설명

다익스트라 알고리즘이 하나의 시작점에서의 다른 vector로 가는 최단경로(거리)를 출력해주는 알고리즘 이었다면 플로이드워셜 알고리즘은 모든지점에서 모든지점을가는 최단경로(거리)를 출력해준다.
예를들어 vector가 6개 있고
다익스트라 알고리즘에서는 start 노드에서부터 나머지 노드까지에서 거리라면

플로이드 워셜 알고리즘은 각 노드들을 1~6의 번호를 붙여준다면
자기자신으로가는 (ex : 1 -> 1, 2 -> 2 , n -> n 인경로)경우를 제외한 36 - 6가지의
모든 경로의 최단거리를 출력해주는 알고리즘이다.

방식

먼저 당연하듯이 그래프에대한 정보 vector의 개수와 edge의 정보들을 입력받는다.
입력받은 정보들을 기반으로 모든 경로의 최단거리를 구하는데 이는 과정만 보면 단순하다.
왜냐하면 말그대로 모든 경로를 확인하며 제일 짧은 것을 택하기 때문이다.

먼저 이 알고리즘에서는 모든 최단경로에대한 정보를 2차원 distance 테이블에 저장한다.
예를들어 노드가 4개라면
step4개 즉 노드의 개수 N번을 반복하는데

step1은 1번 노드를 중간에 거쳐가는 경우를 모두 계산해주고 이 중 가장 작은값으로
갱신해준다
예를들면 노드가 4개이므로
step노드인 1을 제외한 3p2 (3permutation2) 인 6번의 경우가있다.
(이때 D는 2차원 테이블을 의미함)
D[2][3] = min(D[2][3] , D[2][1] + D[1][3])
D[2][4] = min(D[2][4] , D[2][1] + D[1][4])
D[3][2] = min(D[3][2] , D[3][1] + D[1][2])
D[3][4] = min(D[3][4] , D[3][1] + D[1][4])
D[4][2] = min(D[4][2] , D[4][1] + D[1][2])
D[4][3] = min(D[4][3] , D[4][1] + D[1][3])

step4까지 반복하면 모든 경로가 탐색완료되어
테이블 D에 모든 최단거리가 저장되었다.

이때 노드가 N개일때는 NP2(N permutation2) == N * (N-1)
인 경우를 N번의 step만큼 반복하므로
위 알고리즘의 시간복잡도는 O(N^3 - N^2)이고 이는 O(N^3)이라고 볼 수 있다.

코드

#입력 sample
# 4
# 7
# 1 2 4
# 1 4 6
# 2 1 3
# 2 3 7
# 3 1 5
# 3 4 4
# 4 3 2

import sys
input = sys.stdin.readline
INF = int(1e9)

V = (int(input().rstrip()))
E = (int(input().rstrip()))

distance = [[INF] * (V+1) for _ in range(V+1)]

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

#자기자신으로 가는 거리는 0으로 초기화
for i in range(1, V+1):
  distance[i][i] = 0
  
#플로이드 워셜
#V개의 step시작
for k in range(1, V+1):
  for i in range(1, V+1):
    for j in range(1, V+1):
      distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
      


#출력
for i in range(1, V+1):
  for j in range(1, V+1):
    if(distance[i][j] == INF):
      print('INFINITY', end = ' ')
    else:
      print(distance[i][j], end = ' ')
  print()