[알고리즘] 8. 그래프 (3) - 최단 경로/네트워크 플로

// 입력: G=(V,E), s : 시작 정점 // 출력: d[] : s로부터 다른 모든 정점으로의 최단 경로의 길이 // prev[] : 최단 경로를 만드는 선행 정점 Dijkstra (G, s) { S = { }; d[s] = 0; for ( 모든 정점 v ∈ V ) { d[v] = ∞; prev[v] = NULL; } while ( S != V ) { d[u]가 최소인 정점 u ∈ V-S를 선택; S = S ∪ { u }; for ( u에 인접한 모든 정점 v ) { if ( d[v] > d[u] + W(u, v) ) { d[v] = d[u] + W(u, v); prev[v] = u; } } } return ( d[], prev[] ); }

import heapq def dijkstra(graph, start): """ graph: 딕셔너리 형태의 인접 리스트 예) graph[u] = [(가중치, 인접정점), (가중치, 인접정점), ... ] start: 시작 정점 return: d, prev d[v]: start에서 v까지의 최단 거리 prev[v]: start->...->v 최단 경로에서 v 직전에 방문한 정점 """ # 모든 정점에 대해 최단 거리 d[v] = 무한대로 초기화 d = {node: float('inf') for node in graph} prev = {node: None for node in graph} # 시작 정점의 거리만 0으로 설정 d[start] = 0 # 최소 힙(우선순위 큐)에 (거리, 정점) 형태로 삽입 pq = [] heapq.heappush(pq, (0, start)) # 아직 방문하지 않은 정점들을 관리 -> (pq가 빌 때까지) while pq: # 현재 거리가 최소인 정점을 꺼냄 current_dist, u = heapq.heappop(pq) # 이미 저장된 최단 거리보다 크면 무시(과거 정보) if current_dist > d[u]: continue # u와 인접한 각 정점 v에 대해 거리 갱신 시도 for w, v in graph[u]: # (가중치, 인접정점) if d[v] > d[u] + w: d[v] = d[u] + w prev[v] = u # 거리 갱신되면 우선순위 큐에 새로 삽입 heapq.heappush(pq, (d[v], v)) return d, prev if __name__ == "__main__": # 예시 그래프 (인접 리스트) # graph[u] = [(가중치, 인접정점), ...] graph = { 1: [(2, 2), (4, 3)], 2: [(2, 1), (3, 3), (1, 4)], 3: [(4, 1), (3, 2), (5, 4)], 4: [(1, 2), (5, 3)] } start_node = 1 dist, prev = dijkstra(graph, start_node) print(f"최단 거리 배열 (d[]) = {dist}") print(f"선행 정점 배열 (prev[]) = {prev}") # dist[v]를 통해 "start_node에서 v까지의 최단 거리" 확인 가능 # prev[v]를 이용하면 역추적하여 경로를 복원할 수 있음. (1) / \ 2 4 / \ (2)---3---(3) \ / 1 5 \ / (4)

Bellman_Ford(G, s) { for ( 모든 정점 v ∈ V ) { d[v] = ∞; prev[v] = NULL; } d[s] = 0; for ( i = 1; i < n; i++ ) { for ( 모든 간선 (u, v) ∈ E ) if ( d[v] > d[u] + W(u, v) ) { d[v] = d[u] + W(u, v); prev[v] = u; } } return ( d[], prev[] ); }

def bellman_ford(V, E, s): """ 벨만-포드 알고리즘 (단일 시작점 s 로부터의 최단 경로) :param V: 정점들의 리스트 혹은 집합 (ex. [1,2,3,4,...]) :param E: 간선들의 리스트 (ex. [(u, v, w), (u2, v2, w2), ...]) :param s: 시작 정점 :return: (d, prev) d[v] : s 로부터 v 까지의 최단 경로 거리 prev[v]: s -> ... -> v 최단 경로 상에서 v 바로 이전 정점 """ # 1. 거리 배열 d, 이전 정점 배열 prev 초기화 d = {v: float('inf') for v in V} prev = {v: None for v in V} # 시작 정점 s의 거리는 0으로 설정 d[s] = 0 # 2. 모든 간선에 대해 (V-1)번 반복하여 거리 완화(Relaxation) for _ in range(len(V) - 1): for (u, v, w) in E: # 현재 기록된 거리보다 u -> v를 거쳐 가는 경로가 더 짧다면 갱신 if d[u] != float('inf') and d[u] + w < d[v]: d[v] = d[u] + w prev[v] = u # 3. 음수 사이클(Negative Cycle) 검사 # (추가로 원하는 경우, 음수 사이클 존재 여부 확인 가능) for (u, v, w) in E: # 더 갱신될 수 있다면, 음수 사이클 존재 if d[u] != float('inf') and d[u] + w < d[v]: print("Error: 음수 사이클(Negative Cycle)이 존재합니다.") # 필요 시 여기서 별도로 처리(예: 예외 발생, 사이클에 속한 정점 추적 등) break return d, prev # 예시 실행 if __name__ == "__main__": # 예: 정점이 1~5, 간선이 아래와 같다고 가정 V = [1, 2, 3, 4, 5] E = [ (1, 2, 6), (1, 3, 7), (2, 4, 5), (2, 3, 8), (2, 5, -4), (3, 4, -3), (3, 5, 9), (4, 2, -2), (5, 1, 2), (5, 4, 7) ] s = 1 # 시작 정점 d, prev = bellman_ford(V, E, s) print("최단 거리 d:", d) print("이전 정점 prev:", prev)

// 입력: G=(V,E), 인접 행렬 A[1..n][1..n] // 출력: D[][] : 모든 정점 쌍 간의 최단 경로의 길이 Floyd (G) { // D^(0) = ( d_ij^(0) = w_ij ) for (i=1; i<=n; i++) for (j=1; j<=n; j++) D[i][j] = A[i][j]; // D^(k): 경유하는 정점 k for (k=1; k<=n; k++) for (i=1; i<=n; i++) // D_ij for (j=1; j<=n; j++) if (D[i][j] > D[i][k] + D[k][j]) // 경유하는 경우 D[i][j] = D[i][k] + D[k][j]; return (D[][]); }

def floyd_warshall(matrix): """ 플로이드-워셜 알고리즘을 이용해 모든 정점 쌍 최단 경로를 구한다. :param matrix: 그래프의 인접 행렬 (list of lists), matrix[i][j]는 정점 i -> j 로의 가중치 :return: dist (list of lists), dist[i][j]는 i에서 j로 가는 최단 거리 """ # 정점 개수 n n = len(matrix) # dist 배열을 초기 행렬(matrix)로 복사 dist = [row[:] for row in matrix] # 모든 정점 k(경유지)에 대해 for k in range(n): # 모든 출발점 i에 대해 for i in range(n): # 모든 도착점 j에 대해 # 경유지 k를 거치는 경로가 기존보다 더 짧다면 갱신 if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist # 예시 사용 if __name__ == "__main__": import math # 예시: 4개의 정점(0,1,2,3)이 있다고 가정 # 초기 인접 행렬 (가중치) # ∞는 math.inf 로 표현 matrix = [ [0, 5, math.inf, 10], [math.inf, 0, 3, math.inf], [math.inf, math.inf, 0, 1], [math.inf, math.inf, math.inf, 0] ] dist_result = floyd_warshall(matrix) print("플로이드 알고리즘 결과 (모든 쌍 최단 거리):") for row in dist_result: print(row)