모든 정점 사이의 최단경로를 찾는 탐색 알고리즘
시간복잡도 O(n^3)
핵심은 해당 직접 방문하는 경로의 cost와, 다른 곳을 들렀다가 방문하는 cost 를 비교하여 더 작은 값을 선택해 나가는 것
import sys
inf = sys.maxsize
n = 4 #int(input())
a = [[0,2,inf, 4], [2,0,inf, 5],[3,inf,0,inf],[inf,2,1,0]]
dist = [[inf]*n for _ in range(n)]
for i in range(n):
for j in range(n):
dist[i][j] = a[i][j] # a 를 dist에 할당
for k in range(n): # 거치는 점
for i in range(n): # 시작점
for j in range(n): # 끝점
# K를 거쳐을 때의 경로가 더 적은 경로
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j] # 할당
print(dist)