[알고리즘] 최단 경로 플로이드 워셜 알고리즘

[플로이드 워셜 알고리즘]

• 모든 노드에서 다른 모든 노드 까지 최단 경로를 모두 계산한다.
• 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없게 됐다.
• 각 단계마다 \( O(N^2) \) 의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다.
• 시간 복잡도는 \( O(V^2) \)
• 다이나믹 프로그래밍 유형에 속합니다.
• K 번째 단계에 대한 점화식 : \( D_{ab} = min(D_{ab},D_{ak} + D_{kb} ) \)
  - A에서 B로가는 최소 비용과, A에서 K를 거쳐 B로 가는 비용 중 더 작은 값으로 갱신

INF = int(1e9)

n, m = map(int,input().split()) # 노드의 갯수, 간선의 갯수
graph = [[INF]*(n+1) for _ in range(n+1)] # 2차원 리스트, 무한대로 초기화

for i in range(1,n+1):
    graph[i][i] = 0       # 자기 자신한테 가는 비용은 0

for _ in range(m):
    a, b, c = map(int, input().split()) # a에서 b로, 비용은 c
    graph[a][b] = c                     # 그래프에 넣어준다.

for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1, n+1):
            # a에서 b로 가는 최소 경로 비용 업로드
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

 

플로이드 워셜 알고리즘은 결국 모든 경우의 수에 대해 다 비교해보겠다는 것이다.

따라서 당연하게도  경로 for 문 k 가 가장 상위 단계여야 모든 경우의 수에 대해서 다 체크해 볼 수 있겠다.