플로이드-워셜(floyd-warshall) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 다음과 같다.
| 기능 | 특징 | 시간 복잡도(노드 수 : V) |
|---|---|---|
| 모든 노드 간에 최단 경로 탐색 | - 음수 가중치 에지가 있어도 수행할 수 있음 - 동적 계획법의 원리를 이용해 알고리즘에 접근 | O() |
플로이드-워셜의 핵심 이론
플로이드-워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다.
파란색 에지 경로가 1 -> 5 최단 경로라면 1 -> 4 최단 경로와 4 -> 5 최단 경로 역시 파란색 에지로 이뤄질 수밖에 없다. 즉 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이뤄진다는 의미가 된다.
이 원리로 다음과 같은 점화식을 도출할 수 있다.
플로이드-워셜 점화식
- D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])
플로이드-워셜 알고리즘 수행 과정
1. 배열을 선언하고 초기화하기
D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 배열이라 정의한다. S와 E의 값이 같은 칸은 0으로, 다른 칸은 ∞으로 초기화한다.
2. 최단 거리 배열에 그래프 데이터 저장하기
출발 노드는 S, 도착 노드는 E, 에지의 가중치는 W라고 했을 때 D[S][E] = W로 에지의 정보를 배열에 저장한다.
3. 점화식으로 배열 업데이트하기
기존에 구했던 점화식을 3중 for문의 형태로 반복하면서 배열의 값을 업데이트한다.
플로이드-워셜 알고리즘 로직
for 경유지 K에 관해 (1 ~ N)
for 출발 노드 S에 관해 (1 ~ N)
for 도착 노드 E에 관해 (1 ~ N)
D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])
완성된 배열은 모든 노드 간의 최단 거리를 알려 준다.
플로이드-워셜 알고리즘은 모든 노드 간의 최단 거리를 확인해 주기 때문에 시간 복잡도가 O()으로 빠르지 않은 편이다. 이에 따라 플로이드-워셜 알고리즘을 사용햐야 하는 문제가 나오면 일반적으로 노드의 개수의 범위가 다른 그래프에 비해 적게 나타난다.
- Do it! 알고리즘 코딩테스트 자바 편
