플로이드 워셜 알고리즘은 모든 정점 쌍 사이의 최단 거리를 동적 계획법으로 계산하는 알고리즘이다.
그래프 알고리즘 |
|---|
너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · 벨만 포드 알고리즘 · 플로이드 워셜 알고리즘 |
원리
중간 정점으로 k를 허용할 때 d[i][j]와 d[i][k]+d[k][j] 중 작은 값을 선택한다. 전형적인 구현은 O(V³) 시간과 O(V²) 공간을 사용한다.
예시
도시 수가 작고 모든 도시 쌍의 이동 비용이 필요하면 거리 행렬을 한 번 계산한 뒤 질의에 답할 수 있다.
주의할 점
중간 정점 k를 바깥 반복으로 두는 상태 정의를 지켜야 한다. 음수 사이클이 관련된 경로는 유한한 최단 거리가 없으며, 무한대 표시에 대한 덧셈도 별도로 처리한다.