플로이드 워셜 알고리즘

[알고리즘] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) (velog.io)

[알고리즘] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

 

위에 자세하게 나와있다.

 

정리

• 각 노드 사이의 최단 경로를 계산해주는 알고리즘이다. 
• A노드에서 B노드로 가는 경로가 있고, B노드에서 C노드로 가는 경로가 있을 때 A->C의 최단 경로를 다시 계산해준다.
• 따라서 점화식으로는 Edge(A->C) = min(Edge(A->C), Edge(A->B)+Edge(B->C))이다.
• 이때 핵심은 3중 for문 안에 있는 매개가 되는 값인데, 이 값은 가장 최상단의 for문이어야 한다.
• 즉, for(k) -> for(i) -> for(j)와 같은 순서이어야 한다.