Сийрэг граф дээрх Дейкстра¶
Бодлогын томьёолол, хэрэгжүүлэлт ба баталгаа бүхий алгоритмыг Дейкстрагийн алгоритм өгүүллээс олж болно.
Алгоритм¶
Дейкстрагийн алгоритмын complexity-г гаргаж авахдаа бид хоёр хүчин зүйл ашигласныг эргэн саная: хамгийн бага зай $d[v]$-тэй тэмдэглэгдээгүй оройг олох хугацаа, мөн сулруулалтын хугацаа буюу $d[\text{to}]$ утгыг өөрчлөх хугацаа.
Хамгийн энгийн хэрэгжүүлэлтэд эдгээр үйлдэл $O(n)$ ба $O(1)$ хугацаа шаардана. Тиймээс бид эхний үйлдлийг $O(n)$ удаа, хоёр дахийг $O(m)$ удаа гүйцэтгэдэг тул бид $O(n^2 + m)$ complexity-г олж авсан.
Энэ complexity нь нягт графын хувьд, өөрөөр хэлбэл $m \approx n^2$ үед оновчтой байх нь тодорхой. Гэвч $m$ нь ирмэгийн хамгийн их тоо $n^2$-ээс хамаагүй бага байх сийрэг графт эхний гишүүнээс болж complexity бага оновчтой болно. Тиймээс эхний үйлдлийн гүйцэтгэх хугацааг сайжруулах шаардлагатай (мэдээж хоёр дахь үйлдэлд ихээхэн нөлөөлөхгүйгээр).
Үүнийг хийхийн тулд бид олон туслах өгөгдлийн бүтцийн янз бүрийн хувилбарыг ашиглаж болно. Хамгийн үр ашигтай нь Фибоначчийн овоолго бөгөөд энэ нь эхний үйлдлийг $O(\log n)$-д, хоёр дахь үйлдлийг $O(1)$-д гүйцэтгэх боломж олгодог. Тиймээс бид Дейкстрагийн алгоритмын хувьд $O(n \log n + m)$ complexity-г авах ба энэ нь мөн хамгийн богино зам хайх бодлогын онолын хамгийн бага утга юм. Тиймээс энэ алгоритм оновчтой ажилладаг бөгөөд Фибоначчийн овоолго нь оновчтой өгөгдлийн бүтэц юм. Хоёр үйлдлийг хоёуланг нь $O(1)$-д гүйцэтгэж чадах ямар ч өгөгдлийн бүтэц байдаггүй, учир нь энэ нь санамсаргүй тоонуудын жагсаалтыг шугаман хугацаанд эрэмбэлэх боломжийг ч олгох байсан бөгөөд тэр нь боломжгүй юм. Сонирхолтой нь Торупын хамгийн богино замыг $O(m)$ хугацаанд олдог алгоритм байдаг, гэхдээ энэ нь зөвхөн бүхэл жингийн хувьд ажилладаг бөгөөд огт өөр санаа ашигладаг. Тиймээс энэ нь ямар ч зөрчилд хүргэхгүй. Фибоначчийн овоолго энэ даалгаварт оновчтой complexity-г өгдөг. Гэвч тэдгээрийг хэрэгжүүлэхэд нэлээд төвөгтэй бөгөөд бас нэлээд том нуугдмал тогтмолтой.
Буулт хийж та хоёр төрлийн үйлдлийг хоёуланг нь (минимумыг гаргаж авах ба элементийг шинэчлэх) $O(\log n)$-д гүйцэтгэдэг өгөгдлийн бүтэц ашиглаж болно. Тэгвэл Дейкстрагийн алгоритмын complexity нь $O(n \log n + m \log n) = O(m \log n)$ болно.
C++ ийм хоёр өгөгдлийн бүтэц өгдөг: set ба priority_queue.
Эхнийх нь улаан-хар мод дээр, хоёр дахь нь овоолго дээр суурилдаг.
Тиймээс priority_queue нь бага нуугдмал тогтмолтой боловч сул талтай:
энэ нь элемент хасах үйлдлийг дэмждэггүй.
Үүнээс болж бид "тойрч гарах арга" хийх хэрэгтэй болох ба энэ нь үнэндээ $\log n$-ийн оронд $\log m$ гэсэн бага зэрэг муу үржигдэхүүнд хүргэдэг (хэдийгээр complexity-ийн хувьд тэдгээр нь ижил боловч).
Implementation¶
set¶
Let us start with the container set.
Since we need to store vertices ordered by their values $d[]$, it is convenient to store actual pairs: the distance and the index of the vertex.
As a result in a set pairs are automatically sorted by their distances.
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});
}
}
}
}
We don't need the array $u[]$ from the normal Dijkstra's algorithm implementation any more.
We will use the set to store that information, and also find the vertex with the shortest distance with it.
It kinda acts like a queue.
The main loops executes until there are no more vertices in the set/queue.
A vertex with the smallest distance gets extracted, and for each successful relaxation we first remove the old pair, and then after the relaxation add the new pair into the queue.
priority_queue¶
The main difference to the implementation with set is that in many languages, including C++, we cannot remove elements from the priority_queue (although heaps can support that operation in theory).
Therefore we have to use a workaround:
We simply don't delete the old pair from the queue.
As a result a vertex can appear multiple times with different distance in the queue at the same time.
Among these pairs we are only interested in the pairs where the first element is equal to the corresponding value in $d[]$, all the other pairs are old.
Therefore we need to make a small modification:
at the beginning of each iteration, after extracting the next pair, we check if it is an important pair or if it is already an old and handled pair.
This check is important, otherwise the complexity can increase up to $O(n m)$.
By default a priority_queue sorts elements in descending order.
To make it sort the elements in ascending order, we can either store the negated distances in it, or pass it a different sorting function.
We will do the second option.
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});
}
}
}
}
In practice the priority_queue version is a little bit faster than the version with set.
Interestingly, a 2007 technical report concluded the variant of the algorithm not using decrease-key operations ran faster than the decrease-key variant, with a greater performance gap for sparse graphs.
Getting rid of pairs¶
You can improve the performance a little bit more if you don't store pairs in the containers, but only the vertex indices. In this case we must overload the comparison operator: it must compare two vertices using the distances stored in $d[]$.
As a result of the relaxation, the distance of some vertices will change. However the data structure will not resort itself automatically. In fact changing distances of vertices in the queue, might destroy the data structure. As before, we need to remove the vertex before we relax it, and then insert it again afterwards.
Since we only can remove from set, this optimization is only applicable for the set method, and doesn't work with priority_queue implementation.
In practice this significantly increases the performance, especially when larger data types are used to store distances, like long long or double.