플로이드-워셜 알고리즘
플로이드-워셜 알고리즘은 그래프의 모든 정점 쌍에 대해 최단 거리를 계산하는 동적 계획법이다 그래프 알고리즘의 모든 정점 쌍 최단 경로 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전...
| 분류 | 알고리즘 · 그래프 알고리즘 · 모든 정점 쌍 최단 경로 |
|---|---|
| 문제 | 그래프의 모든 정점 쌍에 대해 최단 거리를 계산하는 동적 계획법이다 |
| 입력 | 유한한 최단 경로 의미를 위해 관련 음수 사이클이 없어야 한다 |
| 핵심 단계 | 중간 정점 k를 허용하며 dist[i][j]와 dist[i][k]+dist[k][j] 중 작은 값으로 행렬을 갱신한다 |
| 시간 복잡도 | O(V³) |
| 공간·구현 | 시간 O(V³), 공간 O(V²) |
| 관련 분야 | 그래프, 자료구조 |
| 참고 문헌 | MIT Algorithms |
플로이드-워셜 알고리즘은 그래프의 모든 정점 쌍에 대해 최단 거리를 계산하는 동적 계획법이다 그래프 알고리즘의 모든 정점 쌍 최단 경로 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전제는 유한한 최단 경로 의미를 위해 관련 음수 사이클이 없어야 한다.[1]
핵심 절차는 중간 정점 k를 허용하며 dist[i][j]와 dist[i][k]+dist[k][j] 중 작은 값으로 행렬을 갱신한다. 대각 원소가 음수가 되면 음수 사이클을 감지할 수 있다. 구현에서는 각 정점 또는 간선에 기록된 상태가 어떤 의미를 갖는지 불변식을 정의하고, 탐색·갱신 과정에서 해당 상태를 일관되게 유지해야 한다.
계산 비용은 시간 O(V³), 공간 O(V²) 정점 수를 V, 간선 수를 E라고 나타낼 때 O(V³)의 시간 특성을 가진다. 저장 공간은 그래프의 표현 방식, 큐·스택·우선순위 큐 및 결과 배열의 선택에 영향을 받으므로 실제 적용 시 구현 구조를 함께 분석한다.
작거나 밀집된 그래프의 모든 쌍 거리·도달 가능성에 적합하다. 출발점이 하나면 다익스트라·벨만-포드가 효율적일 수 있다. 대표적인 변형 알고리즘 및 자료구조의 선택은 결과의 최적성, 음수 가중치나 사이클의 허용 여부, 희소·밀집 그래프 여부에 따라 달라진다. 동점 처리와 비연결 그래프 등의 경계 사례까지 정의해야 구현 결과가 명확해진다.[2]