[이론] 플루이드 와샬 Floyd-Warshall

플루이드 와샬

알고리즘

각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인합니다. a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사합니다.

$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$

시간복잡도

3중 for문을 사용해서 O(N^3)입니다.

Success Notice: 수고하셨습니다.