최단 경로 - 플로이드 와샬

다익스트라 알고리즘은 출발 노드에서 다른 노드까지 가는 최단 경로를 특정 노드를 통해 거쳐가는 값을 계산하여 구했다면(제일 적은 비용을 가진 간선만 방문)
플로이드 와샬 알고리즘은 모든 노드에서 모든 노드에 거쳐서 다른 모든 노드로 갈 수 있는 경우의 수를 계산하여 모든 경우의 수에서 가장 적은 값들만 테이블에 갱신하는 알고리즘이다.

위 처럼 최단 거리 테이블을 2차원 배열로 생성하여 처음엔 간선 정보로 테이블을 갱신하고 그 후에 모든 노드에서 다른 모든 노드로 가는 과정을 1번 노드부터 n번 노드 까지 수행하면 된다.

각 단계마다 O(n2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려하므로 총 시간 복잡도는 O(n***3)이다.