다익스트라 알고리즘(Dijkstra's Algorithm)1은 그래프에서 정점과 정점 사이의 최단 경로를 찾을 때 가장 많이 사용되는 알고리즘으로, 유향 그래프와 무향 그래프에서 모두 사용할 수 있으나 가중치가 음수인 간선이 없는 그래프에서만 정상적인 작동을 보장할 수 있다.
다익스트라 알고리즘은 기본적으로 시작 정점이 하나로 고정되어 있으며 작동 원리는 다음과 같다.
1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다.
2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다.
3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다.
4. 아직 선택하지 않은 정점들 중 $d_i$값이 가장 작은 정점 $u$를 선택한다.
5. $u$에서 나가는 간선이 존재하는 각각의 정점 $v$에 대해 $d_v$를 $\min(d_v, d_u + w(u, v))$로 바꾼다.
6. 선택되지 않은 정점이 있다면 4번으로 돌아간다. 그렇지 않은 경우 실행을 종료한다.
알고리즘의 실행이 끝나면 $d_i$에는 정점 $k$로부터 정점 $i$까지의 최단 거리가 저장된다.
4번 과정에서 선택되는 정점은 항상 이전에 선택한 정점들 중 최소한 하나와 인접해 있다. 그렇지 않은 정점들의 $d_i$ 값이 $\infty$로 초기화된 후 변하지 않았을 것임을 생각하면 쉽게 알 수 있다.
그래프가 $n$개의 정점과 $m$개의 간선으로 이루어졌을 때, 알고리즘이 실행되는 동안 정점은 총 $n$번 선택하며 $i$번째 정점을 선택할 때는 $(n-i+1)$개의 정점을 확인해야 한다. 정점을 일일히 확인할 경우 정점을 모두 확인하는 데 $O(n^2)$ 시간이 걸리며, 초기의 다익스트라 알고리즘은 실제로 이 방법을 사용했으나 이후 힙을 사용하여 시간복잡도를 개선했다. 힙에는 (거리, 정점) 쌍이 추가되며 '거리' 값이 작은 쌍부터 힙에서 빠지게 된다. 이를 반영하여 3번 이후의 작동 원리를 다시 나타내면 다음과 같이 된다.
4. 빈 힙에 쌍 $(0, k)$를 삽입한다.
5. 힙에서 '거리' 값이 가장 작은 쌍 하나를 선택한다. 쌍에 저장된 거리가 $x$, 정점 번호가 $u$라고 하자.
6. 선택한 쌍을 힙에서 제거한다.
7. $x = d_u$인 경우, $u$에서 나가는 간선이 존재하는 각각의 정점 $v$에 대해 $d_u + w(u, v) < d_v$라면 $d_v$를 $d_u + w(u, v)$로 바꾸고 힙에 쌍 $(d_u + w(u, v), v)$를 추가한다.
8. 힙이 빈 경우 실행을 종료한다. 그렇지 않은 경우 5번으로 돌아간다.
각각의 간선은 한 번씩만 확인하며, 무향 그래프의 경우 간선의 양 끝 정점을 한번씩 확인하므로 7번 과정에서 정점을 확인하는 횟수의 합은 $O(m)$이다. 따라서 힙에 쌍이 추가되는 횟수는 $O(m)$이라고 할 수 있으며 모든 쌍이 처리되는 시간은 $O(m \lg m)$이다. 이때 그래프에서 고리를 모두 제거하고 중복 간선 중 가중치가 가장 작은 것만 남기면 간선의 개수는 $n^2$보다 작으므로 시간복잡도를 $O(m \lg n^2) = O(2m \lg n) = O(m \lg n)$으로 표기할 수도 있다.
앞에서 자주 예시로 들었던 그래프이다. 정점 $\text{E}$가 시작 정점이라고 하면, $d$ 배열의 초기 상태는 다음과 같다.
편의상 정점 $\text{A}$를 $1$, $\text{B}$를 $2$, $\ldots$, 정점 $\text{I}$를 $9$로 나타내기로 한다. 처음에 힙에 쌍 $(0, 5)$를 추가한다. 다음으로 힙에서 '거리' 값이 가장 작은 쌍인 $(0, 5)$를 선택하고, 정점 $\text{E}$와 인접한 정점들을 체크한다. 이 과정에서 힙에는 쌍 $(2, 2)$와 $(9, 4)$가 추가되고, $d$ 배열은 다음과 같이 변한다.
다음으로 힙에서 빠지는 쌍은 $(2, 2)$이다. 정점 $\text{B}$와 인접한 정점들을 체크하며 $d$ 배열을 갱신한다. 이때는 쌍 $(6, 6)$, $(3, 7)$, $(8, 8)$이 힙에 추가된다. 정점 $\text{E}$의 최단 거리가 갱신되지 않았으므로 쌍 $(4, 5)$는 힙에 추가되지 않는다.
다음으로 힙에서 빠지는 쌍은 $(3, 7)$이다. 정점 $\text{G}$와 인접한 정점들을 체크한다. 쌍 $(10, 9)$가 힙에 추가된다.
다음으로 힙에서 빠지는 쌍은 $(6, 6)$이다. 정점 $\text{F}$와 인접한 정점들을 체크한다. 쌍 $(11, 1)$이 힙에 추가된다.
다음으로 힙에서 빠지는 쌍은 $(8, 8)$이다. 정점 $\text{H}$와 인접한 정점들을 체크하는데, 이번에는 힙에 쌍이 추가되지 않는다.
다음으로 힙에서 빠지는 쌍은 $(9, 4)$이다. 정점 $\text{D}$와 인접한 정점들을 체크한다. 쌍 $(16, 3)$이 힙에 추가된다.
다음으로 힙에서 빠지는 쌍은 $(10, 9)$이다. 정점 $\text{I}$와 인접한 정점들을 체크한다. 쌍 $(14, 3)$이 힙에 추가된다.
다음으로 힙에서 빠지는 쌍은 $(11, 1)$이다. 정점 $\text{A}$와 인접한 정점을 체크한다. 힙에 아무 쌍도 추가되지 않는다.
다음으로 힙에서 빠지는 쌍은 $(14, 3)$이다. 정점 $\text{C}$와 인접한 정점을 체크한다. 힙에 아무 쌍도 추가되지 않는다.
다음으로 힙에서 빠지는 쌍은 $(16, 3)$인데, $16 > d_\text{C}$이므로 인접한 정점을 체크하지 않고 다음으로 넘어간다. 이제 힙이 비었으므로 실행을 종료한다. $d$ 배열의 최종 상태는 다음과 같다.
구현은 다음과 같다. 일반적으로 힙 구조인 std::priority_queue를 사용해서 구현하는데, 여기서는 값이 가장 큰 원소부터 빠지기 때문에 최단 거리의 부호를 바꾸어서 우선순위 큐에 넣는다. 이 코드에서는 $\infty$를 나타내는 값으로 $2^{30}$이 사용되었다. 그래프는 유향 그래프를 기준으로 했는데, 무향 그래프인 경우 $14$행의 주석을 추가하면 나머지는 다르지 않다.
#import<bits/stdc++.h>
using namespace std;
int d[100005];
vector<pair<int, int>>e[100005];
priority_queue<pair<int, int>>Q;
int main()
{
int k, m, n, x, y, z;
cin >> n >> m >> k;
for(int i = 1; i <= m; i++)
{
cin >> x >> y >> z;
e[x].push_back({y, z});
// e[y].push_back({x, z});
}
fill(d + 1, d + n + 1, 1 << 30);
d[k] = 0;
for(Q.push({0, k}); Q.size();)
{
int u = Q.top().second;
x = -Q.top().first;
Q.pop();
if(x == d[u])
{
for(auto &p: e[u])
{
int v = p.first;
if(x + p.second < d[v])
{
d[v] = x + p.second;
Q.push({-d[v], v});
}
}
}
}
}별로 복잡하지 않지만, 구현 시 다양한 종류의 실수가 나올 수 있기 때문에 주의해야 한다. 자세한 내용은 여기에서 확인할 수 있다.
다익스트라 알고리즘을 사용하는 대부분의 그래프에서는 정점 사이의 거리를 경로상에 존재하는 간선의 가중치의 합으로 정의하는데, 가끔씩 거리가 다른 방식으로 정의되는 그래프가 존재한다. 각 간선이 주기가 있는 여러 가중치를 동시에 가지고, 정점 사이의 거리는 시작 정점에서 끝 정점까지 가중치가 증가하는 간선을 따라 이동했을 때 마지막 간선의 가중치와 같은 것으로 정의되는데, 이런 형태의 그래프에서의 최단 거리 역시 다익스트라 알고리즘을 조금 변형해서 구할 수 있다.
[연습문제]
가장 기초적인 문제다. 정점 $K$번 정점에서 모든 정점으로의 최단 경로의 거리를 구하면 된다. 그래프에 고리나 중복 간선이 존재할 수 있음에 유의해야 한다.
이 문제도 기본형에서 추가된 게 없는데 가중치가 $0$인 간선이 존재할 수 있다는 점이 1753번과 다르다. 구현 시 큰 차이는 없지만, 가중치가 $0$인 간선 때문에 Q.pop(); 문장을 if문 뒤로 보낼 수 없다는 차이가 생긴다.
BOJ 20046. Road Reconstruction (Gold IV)
그리드에서 다익스트라 알고리즘으로 두 칸 사이의 최단 거리를 구한다.
마지막에 설명한 특수한 형태의 그래프에서 다익스트라 알고리즘으로 최단 거리를 찾는 문제이다.
BOJ 5719. 거의 최단 경로 (Platinum V)
정점 $u$에서 $v$로 가는 간선의 가중치가 $w$일 때, $d_u + w = d_v$인 경우 그 간선은 최단 경로 중 하나에 포함될 수 있는 간선이다. 이런 간선들을 모두 제거한 다음 남은 간선들로 이루어진 그래프에서 최단 거리를 구하면 된다.
BOJ 24024. 삼색 그래프 (Platinum IV)
분말스프를 최대한 많이 뿌리는 것이 좋음은 쉽게 알 수 있다. 따라서 $X$스푼을 모두 뿌리게 되는데, 분말스프를 빨간색 간선에 뿌리는 횟수와 파란색 간선에 뿌리는 횟수에 따른 최단 경로의 길이는 증가하다가 감소하는 형태로 나타난다. 따라서 삼분 탐색으로 극값을 찾으면 된다.
BOJ 23177. Or Machine (Platinum III)
가중치가 주기로 표현되는 그래프가 등장하는 두 번째 문제. 비트별로 어떤 원소의 비트가 몇 번째 주기에 $1$로 변하는지 빠르게 구하면 된다.
- 때때로 '데이크스트라'로 표기하기도 한다. [본문으로]
'Algorithm > H. Trees & Graphs' 카테고리의 다른 글
| 117. Floyd-Warshall (0) | 2022.03.06 |
|---|---|
| 116. Bellman-Ford (0) | 2022.03.01 |
| 114. Shortest Path (0) | 2021.12.30 |
| 113. Diameter of Tree (0) | 2021.12.29 |
| 112. Bipartite Graph (0) | 2021.12.27 |
