플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
플로이드-워셜 알고리즘이란
플로이드-워셜 알고리즘은 가중치가 있는 그래프에서 모든 정점 쌍 사이의 최단 경로를 구하는 알고리즘이다. 동적 계획법(Dynamic Programming)을 사용하며, 음수 가중치 간선을 처리할 수 있고 음수 사이클 탐지가 가능하다는 특징이 있다.
알고리즘 시각화
동작 원리
플로이드-워셜 알고리즘의 핵심 아이디어는 중간 정점을 거쳐가는 경로를 고려하는 것이다:
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]) // i에서 j로 가는 최단 거리는 기존 경로와 k를 거쳐가는 경로 중 더 짧은 것동작 예시
아래와 같은 그래프가 주어졌을 때 플로이드-워셜 알고리즘의 동작 과정을 살펴보자.
4
A --- B
| |
2 | | 1
| |
C --- D
3간선 목록: A-B(4), A-C(2), B-D(1), C-D(3)
초기 거리 행렬
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 4 | 2 | ∞ |
| B | 4 | 0 | ∞ | 1 |
| C | 2 | ∞ | 0 | 3 |
| D | ∞ | 1 | 3 | 0 |
k=0 (A를 중간 정점으로 사용)
A를 거쳐가는 경로를 고려:
- B→C: B→A→C = 4 + 2 = 6 (기존 ∞보다 작음)
- C→B: C→A→B = 2 + 4 = 6 (기존 ∞보다 작음)
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 4 | 2 | ∞ |
| B | 4 | 0 | 6 | 1 |
| C | 2 | 6 | 0 | 3 |
| D | ∞ | 1 | 3 | 0 |
k=1 (B를 중간 정점으로 사용)
B를 거쳐가는 경로를 고려:
- A→D: A→B→D = 4 + 1 = 5 (기존 ∞보다 작음)
- C→D: C→B→D = 6 + 1 = 7 (기존 3이 더 작음)
- D→A: D→B→A = 1 + 4 = 5 (기존 ∞보다 작음)
- D→C: D→B→C = 1 + 6 = 7 (기존 3이 더 작음)
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 4 | 2 | 5 |
| B | 4 | 0 | 6 | 1 |
| C | 2 | 6 | 0 | 3 |
| D | 5 | 1 | 3 | 0 |
k=2 (C를 중간 정점으로 사용)
C를 거쳐가는 경로를 고려:
- A→D: A→C→D = 2 + 3 = 5 (기존과 동일)
- B→A: B→C→A = 6 + 2 = 8 (기존 4가 더 작음)
- D→A: D→C→A = 3 + 2 = 5 (기존과 동일)
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 4 | 2 | 5 |
| B | 4 | 0 | 6 | 1 |
| C | 2 | 6 | 0 | 3 |
| D | 5 | 1 | 3 | 0 |
k=3 (D를 중간 정점으로 사용)
D를 거쳐가는 경로를 고려:
- A→B: A→D→B = 5 + 1 = 6 (기존 4가 더 작음)
- B→C: B→D→C = 1 + 3 = 4 (기존 6보다 작음)
- C→B: C→D→B = 3 + 1 = 4 (기존 6보다 작음)
최종 거리 행렬
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 4 | 2 | 5 |
| B | 4 | 0 | 4 | 1 |
| C | 2 | 4 | 0 | 3 |
| D | 5 | 1 | 3 | 0 |
최단 경로 예시
- A → D: A → C → D (거리: 2 + 3 = 5)
- B → C: B → D → C (거리: 1 + 3 = 4)
음수 사이클 탐지
플로이드-워셜 알고리즘 실행 후 dist[i][i] < 0인 정점 i가 있으면 음수 사이클이 존재한다.
for (int i = 0; i < V; i++) {
if (dist[i][i] < 0) {
// 음수 사이클 존재
}
}복잡도
| 구분 | 복잡도 | 설명 |
|---|---|---|
| 시간 복잡도 | O(V³) | - 3중 반복문 - k, i, j 각각 V번 반복 |
| 공간 복잡도 | O(V²) | - 거리 행렬: O(V²) |
장단점
| 장점 | 단점 |
|---|---|
| 모든 쌍 최단 경로 - 한 번 실행으로 모든 쌍의 거리 계산 - 반복 호출 불필요 | 느린 속도 - O(V³)로 매우 느림 - 정점이 많으면 비실용적 |
| 음수 가중치 처리 - 음수 간선이 있어도 정상 작동 - 음수 사이클 탐지 가능 | 공간 복잡도 - O(V²) 메모리 필요 - 정점이 많으면 메모리 부족 |
| 간단한 구현 - 3중 반복문으로 간단 - 이해하기 쉬움 | 희소 그래프 비효율 - 간선이 적어도 O(V³) - 다익스트라 V번이 더 효율적 |
| 동적 계획법 - 최적 부분 구조 활용 - 점진적 갱신 | 단일 쌍 비효율 - 하나의 쌍만 필요해도 모든 쌍 계산 - 오버헤드 큼 |
주의사항
- 행렬 초기화: 직접 연결 간선만 가중치, 나머지는 INF, 자기 자신은 0
- 무한대 표현:
Integer.MAX_VALUE / 2사용 (덧셈 오버플로우 방지) - k 루프가 가장 바깥: 반드시 k → i → j 순서로 반복
- 음수 사이클: 알고리즘 완료 후
dist[i][i] < 0인 정점이 있으면 음수 사이클 존재. 이 경우 계산된 모든 거리 값이 유효하지 않으므로 결과를 사용할 수 없음 - 메모리 최적화: 정점이 많으면 공간 초과 주의
구현 팁
- 초기화:
dist[i][i] = 0, 직접 연결 = 가중치, 나머지 = INF - 무한대:
final int INF = 987654321또는Integer.MAX_VALUE / 2 - 반복 순서: 반드시 k → i → j 순서 (다른 순서는 오답)
- 음수 사이클: 알고리즘 완료 후 대각선 확인
dist[i][i] < 0. 탐지 시 결과 사용 불가
Last updated on