플로이드 워셜(Floyd Warshall)

플로이드 워셜(Floyd Warshall)

로버트 플로이드와 스티븐 워셜이라는 컴퓨터 과학자가 고안한 알고리즘

시간복잡도

O(V^3)

사용하는 경우

모든 쌍에 대해 최단거리를 구해야 하는 경우

아이디어

A -> B 경로보다 A -> X -> B로 가는 경로가 더 짧을 경우, 업데이트

방법

1. 2차원 배열 dist[][]를 INF로 초기화.
2. dist[a][b]는 a에서 b로 가는 거리를 뜻하므로, dist[a][a]일 경우 0변경
3. 주어진 경로 거리(가중치) 갱신
4. dist[a][b]에서 노드 k(1<= k <=N)를 경유하였을 때를 가정하여 값을 갱신함 => dist[a][b] > dist[a][k] + dist[k][b] 만족하는 경우, 해당 값으로 갱신 => 모든 쌍 (a, b)에 대해 노드 k를 경유하는 것이 더 좋은지 확인함

정리

3개의 for문으로 이루어진 3중 반복문으로써 비효율적임
즉, 정점의 수가 적거나 모든 쌍에 대한 최단거리를 구해야할 경우에만 사용하는 것이 좋음

 

간선의 개수가 정점의 개수보다 클 경우, 모든 지점에 대한 최단 거리를 구할 때 플로이드-워셜 알고리즘을 사용하는 것이 좋음

(그럼 반대의 경우는 다익스트라 알고리즘을?!)