[알고리즘] 플로이드 와샬 알고리즘

정의

모든 정점에서 모든 정점으로의 최단 경로를 구하는 최단 경로 알고리즘이다.

거쳐가는 기준을 최단거리를 구한다는 특징이 있다.

코드

import math
INF = math.inf

def floyid(graph):    
    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]    
    print(graph)                             
                    
_graph = [
    [0, 5, INF, 8],
    [7, 0, 9, INF],
    [2, INF, 0, 4],
    [INF, INF, 3, 0]
]      

floyd(_graph)