Dijkstra Algorithm¶
You are given a directed or undirected weighted graph with
This problem is also called single-source shortest paths problem.
Algorithm¶
Here is an algorithm described by the Dutch computer scientist Edsger W. Dijkstra in 1959.
Let's create an array
In addition, we maintain a Boolean array
The Dijkstra's algorithm runs for
Evidently, in the first iteration the starting vertex
The selected vertex
After all such edges are considered, the current iteration ends. Finally, after
Note that if some vertices are unreachable from the starting vertex
Restoring Shortest Paths¶
Usually one needs to know not only the lengths of shortest paths but also the shortest paths themselves. Let's see how to maintain sufficient information to restore the shortest path from
Building this array of predecessors is very simple: for each successful relaxation, i.e. when for some selected vertex
Proof¶
The main assertion on which Dijkstra's algorithm correctness is based is the following:
After any vertex
The proof is done by induction. For the first iteration this statement is obvious: the only marked vertex is
Consider the shortest path
First we prove our statement for the vertex
Since the edges' weights are non-negative, the length of the shortest path
On the other hand, since both vertices
From these two inequalities we conclude that
Q.E.D.
Implementation¶
Dijkstra's algorithm performs
The running time of the algorithm consists of:
For the simplest implementation of these operations on each iteration vertex search requires
This complexity is optimal for dense graph, i.e. when
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);
vector<bool> u(n, false);
d[s] = 0;
for (int i = 0; i < n; i++) {
int v = -1;
for (int j = 0; j < n; j++) {
if (!u[j] && (v == -1 || d[j] < d[v]))
v = j;
}
if (d[v] == INF)
break;
u[v] = true;
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;
}
}
}
}
Here the graph pair<int,int>
where the first element in the pair is the vertex at the other end of the edge, and the second element is the edge weight.
The function takes the starting vertex
First of all, the code initializes arrays: distances
After performing all the iterations array
vector<int> restore_path(int s, int t, vector<int> const& p) {
vector<int> path;
for (int v = t; v != s; v = p[v])
path.push_back(v);
path.push_back(s);
reverse(path.begin(), path.end());
return path;
}
References¶
- Edsger Dijkstra. A note on two problems in connexion with graphs [1959]
- Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms [2005]
Practice Problems¶
- Timus - Ivan's Car [Difficulty:Medium]
- Timus - Sightseeing Trip
- SPOJ - SHPATH [Difficulty:Easy]
- Codeforces - Dijkstra? [Difficulty:Easy]
- Codeforces - Shortest Path
- Codeforces - Jzzhu and Cities
- Codeforces - The Classic Problem
- Codeforces - President and Roads
- Codeforces - Complete The Graph
- TopCoder - SkiResorts
- TopCoder - MaliciousPath
- SPOJ - Ada and Trip
- LA - 3850 - Here We Go(relians) Again
- GYM - Destination Unknown (D)
- UVA 12950 - Even Obsession
- GYM - Journey to Grece (A)
- UVA 13030 - Brain Fry
- UVA 1027 - Toll
- UVA 11377 - Airport Setup
- Codeforces - Dynamic Shortest Path
- UVA 11813 - Shopping
- UVA 11833 - Route Change
- SPOJ - Easy Dijkstra Problem
- LA - 2819 - Cave Raider
- UVA 12144 - Almost Shortest Path
- UVA 12047 - Highest Paid Toll
- UVA 11514 - Batman
- Codeforces - Team Rocket Rises Again
- UVA - 11338 - Minefield
- UVA 11374 - Airport Express
- UVA 11097 - Poor My Problem
- UVA 13172 - The music teacher
- Codeforces - Dirty Arkady's Kitchen
- SPOJ - Delivery Route
- SPOJ - Costly Chess
- CSES - Shortest Routes 1
- CSES - Flight Discount
- CSES - Flight Routes