알고리즘 - 플로이드

• 플로이드
  • 모든 노드에서 다른 모든 노드까지 가는데 최소비용, O(V^3)
    • 다익스트라 : 한 노드 -> 다른 모든 노드, O(ElogV)
  • 작동원리
    • 노드 j -> 노드 i 비용 배열 만들기, 초기값 INF
    • 간선의 값을 비용 배열에 반영
    • 모든 노드에 대해 해당 노드 거쳐서 가서 비용 작아질 경우 값 갱신

import sys
INF = sys.maxsize

# 초기값 INF
rs = [[INF]*(n+1) for _ in range(n+1)]

# 자기 자신으로 가는 건 0
for i in range(1,n+1):
	rs[i][i] = 0	

for i in range(m):
    # a에서 b로 가는데 비용(혹은 거리) c
    a,b,c = map(int,input().split())
    # 만약 a에서 b로 가는 길이 여러개이면 : rs[a][b] = min(rs[a][b],c)
    rs[a][b] = c
    

# k : 거치는 곳, j : 시작, i : 도착
for k in range(1,n+1):
	for j in range(1,n+1):
    	for i in range(1,n+1):
        	# 시작에서 도착으로 가는게 k를 거쳐가는 것보다 크면
        	if rs[j][i] > rs[j][k] + rs[k][i]:
            	# 갱신하기
                rs[j][i] = rs[j][k] + rs[k][i]