Floyd Algorithm for Shortest Path

다잌스트라 알고리즘이 한 정점에서 출발했을 때 모든 정점으로의 최단경로를 구하는 알고리즘이었다면
플로이드 알고리즘은 모든 정점에서 모든 정점으로의 최단경로를 구하는 알고리즘이다.

플로이드 알고리즘의 포인트는 '거쳐가는 정점'을 기준으로 최단 거리를 구하는 것이다.

V = 4 # 정점 갯수 
INF = 99999
 
 
def floydWarshall(graph):
   
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
 
    # 중간에 k 를 지나서 도착
    for k in range(V):
        #출발 정점 i
        for i in range(V):
            # 도착정점 j
            for j in range(V):
                # i => j 를 거쳐가는 직방으로 가는 것과 i => k => j, k를 거쳐가는 것 중 작은것을 고려함
                dist[i][j] = min(dist[i][j],
                                 dist[i][k] + dist[k][j])
    printSolution(dist)
 
 
# 결과출력
def printSolution(dist):
    for i in range(V):
        for j in range(V):
            if(dist[i][j] == INF):
                print ("해당 정점에서 정점으로 이동 불가능")
            else:
                print ("%7d\t" % (dist[i][j]),end=' ')
            if j == V-1:
                print ()
 
 # 예시 정점
graph = [[0, 5, INF, 10],
         [INF, 0, 3, INF],
         [INF, INF, 0,   1],
         [INF, INF, INF, 0]
         ]
# Print the solution
floydWarshall(graph)