[Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기

모든 쌍의 최단 경로를 '플로이드 - 와샬' 알고리즘으로 구하는 방법을 알아보고, 구현 코드도 살펴보겠습니다. [ Contents ] 1. 모든 쌍의 최단 경로 위 그래프 그림에서 '노드(Node)'는 원으로 된 지역이고, '간선(Edge)'은 각 지역으로 이동할 수 있는 경로입니다. 간선마다 이동거리 혹은 이동시간에 따른 가중치가 부여됩니다. '모든 쌍의 최단 경로'는 말 그대로, 지역 간 최단거리를 구하는 작업입니다. 보통은 A에서 B로 바로 가면 빠르지만, 경유지를 거쳐서 가는 게 더 지름길일 때도 있죠. 이런 경우를 모두 고려해서 계산해야 합니다. 예를 들어, 위 경로에서는 1->3으로 바로 가는 것보다, 2를 경유해서 가는 게 더 빠릅니다. 2. 플로이드 - 와샬(Floyd-Warshall) 알..

원문링크 : [Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기