최단 경로 - 플로이드 워셜 알고리즘 (Floyd-Warshal)

다익스트라 알고리즘이 특정 한 노드에서 모든 노드로의 최단 경로를 계산했다면,
플로이드 워셜 알고리즘은 모든 노드에서 모든 노드로의 최단 경로를 계산한다.

다익스트라 알고리즘에서는 매 단계 마다 시작 노드로부터 최단 경로가 가장 짧은 특정 노드를 선택하고 그 외 모든 노드에 대해 해당 노드를 거쳐 가는 경로를 계산하여 최단 경로 테이블을 갱신했다.

플로이드 워셜의 경우 매 단계마다 모든 노드에 대해 해당 노드를 거쳐 가는 최단 경로를 계산하고 최단 거리 테이블을 갱신한다.

먼저, 최단 경로 테이블을 초기화 한다. 플로이드 워셜의 경우 모든 노드에서 모든 노드에 대한 최단 경로를 모두 구해야하기 때문에 최단 경로 테이블은 2차원 리스트가 된다.
그리고 다음과 같은 과정을 반복한다.

1. 한 노드를 선택하고 그외 모든 노드 n-1P2 개를 선택한다.
   (예를 들어 현재 단계에서 선택된 노드가 k이고 k 외의 a, b노드를 선택)
2. a->b로 가는 최단 경로와 a->k->b로 가는 최단 경로를 비교하여 k를 거쳐 가는 비용이 적다면 테이블을 갱신한다.
3. 모든 n 개 노드에 대해 그외 모든 n-1P2 노드의 최단 거리를 계산하여 갱신한다.

위 1, 2, 3 과정을 반복하면 되는데 n개에 노드에 대해 n-1P2개의 노드를 선택해야 하므로 시간 복잡도는 O(N3)을 가진다.

파이썬을 통한 코드는 아래와 같다.

#Floyd-Warshal 

INF = int(1e9)
n, m = map(int, input().split())

graph = [ [INF] * (n+1) for _ in range(n+1) ] 
for i in range(1, n+1):
  graph[i][i] = 0

for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a][b] = c

for i in range(1, n+1):
  for a in range(1, n+1):
    for b in range(1, n+1):
      graph[a][b] = min(graph[a][b], graph[a][i] + graph[i][b])

for a in range(1, n+1):
  for b in range(1, n+1):
    if graph[a][b] == INF:
      print("INFINITY", end = " ")
    else:
      print(graph[a][b], end = " ")

  print()