희소 그래프에서의 Dijkstra¶
문제 설명과 구현 및 증명을 포함한 알고리즘은 Dijkstra 알고리즘 문서에서 확인할 수 있습니다.
알고리즘¶
Dijkstra 알고리즘의 복잡도를 유도할 때 두 가지 요소를 사용했다는 점을 다시 떠올려 봅시다. 하나는 거리 $d[v]$가 가장 작은 미표시 정점을 찾는 시간이고, 다른 하나는 완화(relaxation) 시간, 즉 값 $d[\text{to}]$를 변경하는 시간입니다.
가장 단순한 구현에서 이 연산들은 각각 $O(n)$과 $O(1)$의 시간이 필요합니다. 따라서 첫 번째 연산을 $O(n)$번, 두 번째 연산을 $O(m)$번 수행하므로 복잡도는 $O(n^2 + m)$이 됩니다.
이 복잡도가 밀집 그래프, 즉 $m \approx n^2$인 경우에 최적이라는 것은 분명합니다. 그러나 $m$이 최대 간선 수 $n^2$보다 훨씬 작은 희소 그래프에서는 첫 번째 항 때문에 복잡도가 최적에서 멀어집니다. 따라서 첫 번째 연산의 실행 시간을 개선해야 합니다(물론 두 번째 연산에는 크게 영향을 주지 않으면서 말입니다).
이를 위해 여러 가지 보조 자료 구조를 활용할 수 있습니다. 가장 효율적인 것은 피보나치 힙으로, 첫 번째 연산을 $O(\log n)$에, 두 번째 연산을 $O(1)$에 수행할 수 있게 해 줍니다. 따라서 Dijkstra 알고리즘의 복잡도는 $O(n \log n + m)$이 되며, 이는 최단 경로 탐색 문제의 이론적 하한이기도 합니다. 그러므로 이 알고리즘은 최적으로 동작하며, 피보나치 힙은 최적의 자료 구조입니다. 두 연산을 모두 $O(1)$에 수행할 수 있는 자료 구조는 존재하지 않습니다. 그런 자료 구조가 있다면 임의의 수 목록을 선형 시간에 정렬할 수 있게 되는데, 이는 불가능하기 때문입니다. 흥미롭게도 Thorup이 제안한, $O(m)$ 시간에 최단 경로를 찾는 알고리즘이 존재하지만, 이 알고리즘은 정수 가중치에서만 동작하며 완전히 다른 아이디어를 사용합니다. 따라서 이는 어떠한 모순도 일으키지 않습니다. 피보나치 힙은 이 작업에 대해 최적의 복잡도를 제공합니다. 그러나 구현이 상당히 복잡하고, 숨겨진 상수도 꽤 큽니다.
절충안으로, 두 종류의 연산(최솟값 추출과 항목 갱신)을 모두 $O(\log n)$에 수행하는 자료 구조를 사용할 수 있습니다. 그러면 Dijkstra 알고리즘의 복잡도는 $O(n \log n + m \log n) = O(m \log n)$이 됩니다.
C++은 이러한 자료 구조를 두 가지 제공합니다. 바로 set과 priority_queue입니다. 전자는 레드-블랙 트리에 기반하고, 후자는 힙에 기반합니다. 따라서 priority_queue는 숨겨진 상수가 더 작지만, 원소를 삭제하는 연산을 지원하지 않는다는 단점이 있습니다. 이 때문에 "우회 방법"을 사용해야 하며, 이로 인해 실제로는 $\log n$ 대신 약간 더 나쁜 인자 $\log m$이 생깁니다(복잡도 측면에서는 둘이 동일하지만 말입니다).
구현¶
set¶
먼저 컨테이너 set부터 살펴봅시다. 정점들을 값 $d[]$에 따라 정렬된 상태로 저장해야 하므로, 거리와 정점 번호로 이루어진 쌍 자체를 저장하는 것이 편리합니다. 그 결과 set 안에서 쌍들은 거리에 따라 자동으로 정렬됩니다.
const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;
void dijkstra(int s, vector<int> & d, vector<int> & p) {
int n = adj.size();
d.assign(n, INF);
p.assign(n, -1);
d[s] = 0;
set<pair<int, int>> q;
q.insert({0, s});
while (!q.empty()) {
int v = q.begin()->second;
q.erase(q.begin());
for (auto edge : adj[v]) {
int to = edge.first;
int len = edge.second;
if (d[v] + len < d[to]) {
q.erase({d[to], to});
d[to] = d[v] + len;
p[to] = v;
q.insert({d[to], to});
}
}
}
}
일반적인 Dijkstra 알고리즘 구현에서 사용하던 배열 $u[]$는 이제 더 이상 필요하지 않습니다. 그 정보는 set에 저장하고, 최단 거리를 가진 정점도 이 set을 이용해 찾습니다. 이는 일종의 큐처럼 동작합니다. 메인 루프는 set/큐에 정점이 하나도 남지 않을 때까지 실행됩니다. 거리가 가장 작은 정점을 꺼내고, 완화에 성공할 때마다 먼저 이전 쌍을 제거한 뒤 완화를 마치면 새 쌍을 큐에 추가합니다.
priority_queue¶
set을 사용한 구현과의 주된 차이점은 C++를 비롯한 많은 언어에서 priority_queue의 원소를 제거할 수 없다는 것입니다(이론적으로는 힙이 이 연산을 지원할 수 있기는 합니다). 따라서 우회 방법을 써야 합니다. 이전 쌍을 큐에서 삭제하지 않고 그대로 둡니다. 그 결과 하나의 정점이 서로 다른 거리로 동시에 큐에 여러 번 나타날 수 있습니다. 이러한 쌍 중에서 관심 있는 것은 첫 번째 원소가 $d[]$의 해당 값과 같은 쌍뿐이며, 나머지 쌍은 모두 오래된 쌍입니다. 따라서 약간의 수정이 필요합니다. 각 반복을 시작할 때 다음 쌍을 꺼낸 후, 그것이 중요한 쌍인지 아니면 이미 처리된 오래된 쌍인지 확인합니다. 이 확인은 중요합니다. 이 확인을 하지 않으면 복잡도가 $O(n m)$까지 증가할 수 있습니다.
기본적으로 priority_queue는 원소를 내림차순으로 정렬합니다. 원소를 오름차순으로 정렬하게 하려면 거리의 부호를 반전하여 저장하거나, 다른 정렬 함수를 전달하면 됩니다. 여기서는 두 번째 방법을 사용하겠습니다.
const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;
void dijkstra(int s, vector<int> & d, vector<int> & p) {
int n = adj.size();
d.assign(n, INF);
p.assign(n, -1);
d[s] = 0;
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({0, s});
while (!q.empty()) {
int v = q.top().second;
int d_v = q.top().first;
q.pop();
if (d_v != d[v])
continue;
for (auto edge : adj[v]) {
int to = edge.first;
int len = edge.second;
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
p[to] = v;
q.push({d[to], to});
}
}
}
}
실제로는 priority_queue 버전이 set 버전보다 조금 더 빠릅니다.
흥미롭게도, 2007년 기술 보고서는 decrease-key 연산을 사용하지 않는 알고리즘 변형이 decrease-key 변형보다 더 빠르게 실행되었으며, 희소 그래프에서 성능 차이가 더 컸다고 결론지었습니다.
쌍 없애기¶
컨테이너에 쌍을 저장하지 않고 정점 인덱스만 저장하면 성능을 조금 더 향상할 수 있습니다. 이 경우 비교 연산자를 오버로드해야 합니다. 비교 연산자는 $d[]$에 저장된 거리를 사용하여 두 정점을 비교해야 합니다.
완화의 결과로 일부 정점의 거리가 바뀝니다. 하지만 자료 구조는 스스로 자동으로 재정렬되지 않습니다. 실제로 큐에 있는 정점의 거리를 변경하면 자료 구조가 망가질 수 있습니다. 앞에서와 마찬가지로 정점을 완화하기 전에 제거하고, 완화한 뒤에 다시 삽입해야 합니다.
원소를 제거할 수 있는 것은 set뿐이므로, 이 최적화는 set 방식에만 적용할 수 있으며 priority_queue 구현에서는 동작하지 않습니다. 실제로 이 방법은 성능을 크게 향상하며, 특히 long long이나 double처럼 더 큰 자료형으로 거리를 저장할 때 효과가 큽니다.