[Algorithm] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘이란?

 

변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 다익스트라 알고리즘이 하나의 노드로부터 최단경로를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍들에 대한 최단거리를 구하는 알고리즘이다.

 

플로이드-워셜의 특징

• 가능한 모든 정점 2개의 조합에 대한 최단 경로를 구하는 ASP(All Pairs Shortest Path) 알고리즘
• 두 정점 사이의 최단 경로에 포함될 수 있는 모든 정점의 경우를 고려하는 dp 접근
• 정점의 수를 V, 간선의 수를 E라고 할 때, 시간 복잡도는 O(V^3)