Floyd - Warshall’s Algorithm
최단 경로를 구하는 과정에서 사용되는 여러 알고리즘 중 모든 노드에서 또 다른 모든 노드까지의 최단 거리를 구하기 위해서 사용되는 알고리즘이다.
최단 경로를 구할 때 사용되는 다른 알고리즘으로 Dijkstra’s Algorithm가 사용된다. (두 알고리즘 비교에 대해서는 따로 정리할 예정이다.)
정의
Floyd - Warshall’s Algorithm 은 모든 정점에 대하여 최단경로를 구하는 알고리즘이다.
주어지는 그래프에서 두 노드의 최단 거리를 구할 때 사용이 되며, 모든 노드 쌍에 대해서도 최단거를 구할 수 있다.
해당 알고리즘 동작은 동적 프로그래밍을 기반으로 수행을 한다. 그리고 삼중 반복문을 이용하여 모든 쌍의 최단거리를 구하는 것이 핵심 동작이라고 생각을 한다.
알고리즘 동작 중 최단거리를 구하는 방법은 바로 앞에서 이야기 했던 동적 프로그래밍 방법을 이용하여 각 노드에 대한 다른 노로 가는 최단거리를 다른 노드를 거쳐서 더 짧은 경로를 찾아 갱신하는 원리이다.
알고리즘 적용 범위
- 모든 쌍의 최단 경로를 구할 때 주로 사용
- 가중치 그래프에서 동작하지만, 가중치가 음수인 간선이 있을 수 있다. (단, 음수 사이클이 없어야 함)
- 간선이 많은 그래프, 매우 큰 그래프에도 유용하
알고리즘 구현 핵심 포인트
- 3중 루프
- 각 정점 k를 중간 노드로 두고, i에서 k를 거쳐 j로 가는 경로가 더 짧은지 확인하면서 갱신함
- 최단 경로 갱신:
- distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
- 즉, i에서 j로 가는 경로가 직접 연결된 경로보다 중간 노드를 거친 경로가 더 짧으면 갱신함
- 초기화:
- 자기 자신으로 가는 거리는 0으로 설정하고, 연결되지 않은 노드 간의 거리는 무한대로 설정함
- 음수 사이클 처리:
- 만약 음수 사이클이 있다면, 이 알고리즘은 제대로 작동하지 않으므로, 이를 검출하는 로직이 필요함
단계별 동작 과정
동작 과정을 알아보기 위해서 간단한 예제에 적용 하겠다.
2 // 정점 : A, B ,C ,D
A -------- B // 가중치는 옆에와 동일하다.
| | // 각 노드에서 다른 노드까지의 거리
4 | | 1 | Node | A | B | C | D |
| | | A | 0 | 2 | 4 | ♾️ |
C -------- D | B | 2 | 0 | ♾️ | 1 |
3 | C | 4 | ♾️ | 0 | 3 |
| D | ♾️ | 1 | 3 | 0 | | Node | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 2 | 4 | ♾️ |
| B | 2 | 0 | ♾️ | 1 |
| C | 4 | ♾️ | 0 | 3 |
| D | ♾️ | 1 | 3 | 0 |
초기화
주어진 그래프 정보를 이용하기 위해서 크기에 맞는 배열을 값을 초기화 해줘야 한다.
일단 특정 노드에서 다른 노드로의 가중치는 아직 모르기 때문에 무한대의 수로 저장을 한다,
최단거리 계산
최단거리 갱신에 있어서 사용될 간단한 예시 코드는 아래와 같다,
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// i -> j 경로가 없을 경우, i -> k 경로와 k -> j 경로를 거쳐서 가는 게 더 좋은지 확인
if (distance[i][j] > distance[i][k] + distance[k][j]) {
distance[i][j] = distance[i][k] + distance[k][j];
}
}
}
}세 번째 for문에서 각 정점 k를 중간 노드로 두고, i에서 j로 가는 경로가 중간에 k를 거친 경로가 더 짧다면 갱신한다.
결과
위 과정을 바탕으로 모든 노드에서 다른 노드 까지의 최단 거리 계산이 완료 되었다.
| Node | A | B | C | D |
|:----:|:-----:|:-----:|:-----:|:-----:|
| A | 0 | 2 | 4 | 3 |
| B | 2 | 0 | 3 | 1 |
| C | 4 | 3 | 0 | 3 |
| D | 3 | 1 | 3 | 0 |
마무리
Floyd-Warshall 알고리즘은 모든 정점 쌍 간의 최단 거리를 효율적으로 계산할 수 있는 강력한 알고리즘으로, 특히 가중치가 있는 방향 그래프에서 유용하게 사용된다
삼중 반복문을 활용하여 각 노드를 경유지로 설정하면서 거리 값을 갱신하는 방식은 동적 프로그래밍의 전형적인 활용 예시 중 하나이다.
단, 음수 사이클이 존재할 경우 결과가 왜곡될 수 있다, 이를 미리 탐지하는 처리가 필요하며, 노드 수가 많을 경우 시간 복잡도 O(N³) 이라는 점도 고려해야 한다.
실전에서는 그래프의 크기와 간선 특성을 파악한 뒤, Dijkstra 등 다른 알고리즘과의 특성을 비교해가며 선택적으로 사용하는 것이 좋다.
