Learn about Dijkstra's algorithm
You are given a directed or undirected weighted graph with vertices and edges. All edge weights are non-negative. You are also given a starting vertex .
For each vertex , we need to find the length of the shortest path from to .
We use two arrays:
d[] — for each vertex x, d[x] stores the current shortest known distance from s to x;used[] — shows whether the vertex has already been marked.Initially:
d[s] = 0d[x] = infThen we perform up to iterations. In each iteration:
x with the smallest value d[x];x.If there is an edge (x, to) of weight len, then relaxation means:
At the end, the array d[] contains the lengths of the shortest paths from s to all vertices.
If some vertices are unreachable from s, their distances remain equal to infinity. In that case, the algorithm can stop as soon as the chosen vertex has infinite distance.
The previous implementation spends time in each iteration to find the unmarked vertex with minimum distance. This is the slowest part of the algorithm and leads to a total complexity of .
We can improve this by storing all unmarked vertices in a data structure that supports:
One way to do this is with:
We store pairs (d[x], x) in the set. Then the smallest element is always at begin().
When a distance improves during relaxation, we remove the old pair and insert the new one.
This reduces the complexity to:
const int inf = 1e9;
vector<int> dijkstra(int n, int s, vector<vector<pair<int, int>>>& v) {
vector<int> d(n, inf);
vector<bool> used(n, false);
d[s] = 0;
for (int i = 0; i < n; i++) {
int x = -1;
// 1. find the unmarked vertex with minimum distance
for (int j = 0; j < n; j++) {
if (!used[j] && (x == -1 || d[j] < d[x])) {
x = j;
}
}
if (x == -1 || d[x] == inf) {
break;
}
// 2. mark the current vertex
used[x] = true;
// 3. relaxations
for (auto edge : v[x]) {
int to = edge.first;
int len = edge.second;
d[to] = min(d[to], d[x] + len);
}
}
return d;
}
set<pair<int, int>>
const int inf = 1e9;
vector<int> dijkstra(int n, int s, vector<vector<pair<int, int>>>& v) {
vector<int> d(n, inf);
d[s] = 0;
set<pair<int, int>> S;
for (int i = 0; i < n; i++) {
S.insert({d[i], i});
}
while (!S.empty()) {
// 1. get the unmarked vertex with minimum distance
int x = S.begin()->second;
int dist = S.begin()->first;
S.erase(S.begin());
if (dist == inf) {
break;
}
// 2. relaxations
for (auto edge : v[x]) {
int to = edge.first;
int len = edge.second;
if (d[x] + len < d[to]) {
S.erase({d[to], to}); // remove old value
d[to] = d[x] + len;
S.insert({d[to], to}); // insert updated value
}
}
}
return d;
}