재원블로그 재원블로그

대표적인 최단 경로 알고리즘 중에서 3번째 플로이드 워셜 알고리즘이다. 플로이드 워셜 알고리즘은 다익스트라나 벨만-포드와 다르게 1:N이 아닌 N:N 의 최단 시간을 찾을 수 있다. 최악 시간 복잡도는 O(|V|^3) 이다. 플로이드 워셜 알고리즘은 처음에 간선들의 정보와 자기 자신으로의 경로는 0이라는 정보만 주고, 모든 정점들의 경유를 하나씩 열면서 직접 가는 것보다 경유하는게 더 짧은지를 확인한다. 플로이드 워셜은 음수 사이클이 없는 그래프에서 음수 가중치가 있어도 사용할 수 있다. C++로 구현한 코드는 다음과 같다. #define INF 1000000000 int n; vector edges; vector floyd_warshall() { vector dist(n + 1, vector(n + 1..