플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 탐색하는 알고리즘이다. 다음과 같은 그래프가 존재할 때, 각각의 정점이 다른 정점으로 가는 거리(비용)을 2차원 배열로 나타내면 아래와 같다. 0 5 INF(무한) 8 7 0 9 INF(무한) 2 INF(무한) 0 4 INF(무한) INF(무한) 3 0 위 표는 현재까지 계산된 최소 비용이며, 이러한 2차원 배열을 반복적으로 갱신하여 모든 최소 비용을 구하는 과정은 아래와 같다. (1) 노드 1을 거쳐가는 경우 [ 2->3 ] 노드 1을 거쳐가야 하기 때문에 1을 포함하지 않은 경우들만 계산해주면 된다. 0 5 INF(무한) 8 7 0 [ 2->3 ] [ 2->4 ] 2 [ 3->2 ] 0 [ 3->4 ] INF..
