[알고리즘] 플로이드 와샬 (Floyd Wharshall) 알고리즘

개념 플로이드 와샬 알고리즘은 '거쳐가는 정점' 을 기준으로 최단 거리를 구하는 알고리즘을 수행한다. '모든 정점'에서 '모든 정점'으로의 최단 경로를 구할 때 사용한다.

특징 '거쳐가는 정점'을 기준으로 최단 거리를 구한다. 시간 복잡도는 O(N^3) 이다.

과정 위와 가튼 그래프가 존재한다고 할 때, 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열의 형태로 출력하면 다음과 같다. 이 테이블은 '현재까지 계산된 최소 비용' 이다.

이러한 이차원 배열을 반복적으로 갱신하여 최종적인 모든 최소 비용을 구할 것이다. 이 때, 반복의 기준이 '거쳐가는 정점'인 것. 1.

노..........