플로이드-와샬을 사용 해야 할 경우! 플로이드-와샬 알고리즘은 "모든 정점 쌍에 대해 최단 거리를 구할 떄 " 사용한다. 즉, 모든 정점의 최단거리를 구하고 싶을 떄 다익스트라나 밸만-포드가 아닌 플로이드-와샬 알고리즘을 사용하면 된다. 플로이드 알고리즘은 그래프의 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 map[][]을 계산한다. map[u][v]의 의미는 정점 u에서 정점 v로 가는 최단거리를 나타낸다. 플로이드 알고리즘의 경로와 경유점의 개념 두 정점 u와 v를 이어주는 경로가 있을 때, 이 경로는 항상 u와 v를 지난다. 이 외에도 다른 정점을 거칠 수 있다. 정점 u에서 정점 v로 가는 최단 경로를 D(u,v)라고 하자. 정점 a에서 정점 b로 갈때 5만큼의 비용이 드는데, c,d를 거..