다익스트라 알고리즘(Dijkstra's Algorithm): 가중치 그래프 최단 경로 찾기
Graph에 대해 다루면서 BFS에 대해 알아본 적이 있다. BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용하지만, 현실에서 더 많이 활용되는 가중치가 있는 그래프에서 최단 경로를 보장하지 못한다. 그래서 이번 포스팅에서는 가중치 그래프(weighted graph)에서 최단 경로를 찾는 탐욕 알고리즘(greedy algorithm)과 그 대표적인 예시인 다익스트라 알고리즘(Dijkstra's algorithm)에 대해 자세히 알아보겠다.
1. BFS의 한계와 탐욕 알고리즘
BFS는 각 edge의 가중치가 동일하다고 가정하고 최단 경로를 찾는다. 하지만 실제 세상의 많은 문제는 edge의 가중치가 다를 수 있다. 예를 들어, 도시 간의 거리, 항공권 가격, 네트워크 지연 시간 등은 모두 가중치로 표현될 수 있다. 이러한 가중치 그래프에서 최단 경로를 찾기 위해서는 BFS를 변형하거나 다른 알고리즘을 사용해야 한다.
탐욕 알고리즘(Greedy Algorithm)은 각 단계에서 가장 '좋아 보이는' 선택을 하는 알고리즘이다. 탐욕 알고리즘은 항상 최적의 해를 보장하지는 않지만, 많은 경우 효율적이고 간단한 해결책을 제시한다. 다익스트라 알고리즘은 가중치 그래프에서 최단 경로를 찾는 탐욕 알고리즘의 대표적인 예시다.
2. 다익스트라 알고리즘 (Dijkstra's Algorithm)
다익스트라 알고리즘은 시작 정점(source vertex)에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 음수 가중치를 갖는 edge가 없는 그래프에서만 사용할 수 있다.
2.1. Cloud (클라우드)와 Edge Relaxation (간선 완화)
다익스트라 알고리즘은 Cloud(클라우드)라는 개념을 사용한다. Cloud는 시작 정점에서부터 최단 경로가 확정된 정점들의 집합이다. 알고리즘은 Cloud를 점차 확장해 나가면서 모든 정점까지의 최단 경로를 찾는다.
Edge Relaxation(간선 완화)은 Cloud에 새롭게 추가된 정점 u를 이용하여 Cloud 외부의 정점 z까지의 거리(d(z))를 업데이트하는 과정이다. 간선 (u, z)에 대해 다음과 같이 d(z)를 갱신한다.
d(z) = min{d(z), d(u) + weight(u, z)}
즉, 기존의 d(z) 값과 u를 거쳐 z로 가는 경로의 길이 중 더 작은 값으로 d(z)를 업데이트한다.
 |
| edge relaxtion |
2.2. 다익스트라 알고리즘 작동 방식
- 시작 정점 s의 거리 d(s)를 0으로 설정하고, 나머지 정점들의 거리를 무한대로 설정
- Cloud를 시작 정점 s만 포함하는 집합으로 초기화
- Cloud에 속하지 않은 정점 중 거리가 가장 짧은 정점 u를 Cloud에 추가
- 정점 u에 인접한 모든 간선에 대해 Edge Relaxation을 수행
- 3-4 단계를 모든 정점이 Cloud에 포함될 때까지 반복
2.3. 다익스트라 알고리즘 예시
다음과 같은 가중치 그래프에서 정점 A에서 다른 모든 정점까지의 최단 경로를 다익스트라 알고리즘을 사용하여 구해보자.
B
/ \
4 / \ 8
/ \
A ----- C
\ /
7 \ / 1
\ /
D
- 초기화: d(A) = 0, d(B) = d(C) = d(D) = ∞, Cloud = {A}
- B, C, D 중 가장 작은 d 값을 가진 정점 C를 Cloud에 추가하고, C에 인접한 간선 (C, D)에 대해 Edge Relaxation을 수행, d(D) = min(∞, 1) = 1, Cloud = {A, C}
- B, D 중 가장 작은 d 값을 가진 정점 D를 Cloud에 추가하고, D에 인접한 간선은 없으므로 Edge Relaxation을 수행하지 않음, Cloud = {A, C, D}
- B를 Cloud에 추가하고, B에 인접한 간선 (B, A)에 대해 Edge Relaxation을 수행, d(A) = min(0, 12) = 0, Cloud = {A, B, C, D}
따라서 정점 A에서 다른 모든 정점까지의 최단 경로는 다음과 같다.
- A -> C -> D (총 거리 1)
- A -> B (총 거리 4)
3. 왜 다익스트라 알고리즘은 음수 가중치 간선에서 작동하지 않을까?
다익스트라 알고리즘은 탐욕 알고리즘이기 때문에, 각 단계에서 최선의 선택을 한다고 가정한다. 하지만 음수 가중치 간선이 존재하는 경우, 이 가정이 깨질 수 있다. 예를 들어, 특정 정점까지의 최단 경로가 이미 결정되었다고 생각했지만, 음수 간선에 의해 나중에 더 짧은 경로가 발견될 수 있다.
4. 음수 가중치 간선에도 작동하는 Bellman-Ford 알고리즘
Bellman-Ford 알고리즘은 음수 가중치 간선이 있는 그래프에서도 최단 경로를 찾을 수 있는 알고리즘이다. 이 알고리즘은 모든 간선에 대해 반복적으로 Edge Relaxation을 수행하며, 음수 사이클(negative cycle)이 존재하는지도 확인할 수 있다. Bellman-Ford 알고리즘의 시간 복잡도는 O(VE)다. (V는 정점의 수, E는 간선의 수)
마무리하며
이번 포스팅에서는 가중치 그래프에서 최단 경로를 찾는 Dijkstra's 알고리즘에 대해 알아보았다. Dijkstra's 알고리즘은 음수 가중치 간선이 없는 그래프에서 효율적으로 작동하며, Cloud와 Edge Relaxation 개념을 사용하여 최단 경로를 찾다. 다음 포스팅에서는 minimum spanning tree에 대해 알아보겠다.
추천글:
[자료구조] Directed graph - Floyd-Warshall Transitive Closure, Topological sorting
(https://hyeonb.blogspot.com/2024/06/directed-graph-floyd-warshall.html)
(https://hyeonb.blogspot.com/2024/06/dfs-bfs.html)
(https://hyeonb.blogspot.com/2024/06/graph.html)
