Best-First: Dijkstra’s Algorithm
Learn about Dijkstra’s algorithm and its applications in solving the shortest paths problem.
We'll cover the following...
Proof of tenseness property in Dijkstra’s algorithm
If we replace the FIFO queue in breadth-first search with a priority queue, where the key of a vertex is its tentative distance , we obtain an algorithm first published in 1957 by a team of researchers at the Case Institute of Technology led by Michael Leyzorek, in an annual project report for the Combat Development Department of the US Army Electronic Proving Ground. The same algorithm was independently discovered by Edsger Dijkstra in 1956 (but not published until 1959), again by George Minty sometime before 1960, and again by Peter Whiting and John Hillier in 1960. A nearly identical algorithm was also described by George Dantzig in 1958. Although several early sources called it “Minty’s algorithm,” this approach is now universally known as “Dijkstra’s algorithm,” in full accordance with Stigler’s Law. The pseudocode for this algorithm is shown below.
An easy induction proof implies that at all times during the execution of this algorithm, an edge is tense if, and only if, vertex is either in the priority queue or is the vertex most recently from the priority queue. Thus, Dijkstra’s algorithm is an instance of Ford’s general strategy, which implies that it correctly computes shortest paths, provided there are no negative cycles in .
The images below show computing shortest paths in a dag by relaxing outgoing edges in topological order. In each iteration, bold edges indicate predecessors, and the bold vertex is about to be scanned.
Algorithm
Implementation
#include <iostream>#include <vector>#include <queue>#include <limits.h>using namespace std;// Edge data structurestruct Edge{int v; // destination vertexint weight; // weight of the edgeEdge(int _v, int _w): v(_v), weight(_w) {}};// Graph data structurestruct Graph{int V; // number of verticesvector<vector < Edge>> adj; // adjacency listGraph(int _V): V(_V){adj.resize(V);}void addEdge(int u, int v, int w){adj[u].push_back(Edge(v, w));}};// Initialize single source shortest pathvoid initSSSP(int s, vector<int> &dist){fill(dist.begin(), dist.end(), INT_MAX);dist[s] = 0;}// Dijkstra's algorithmvoid dijkstra(int s, Graph &G){priority_queue<pair<int, int>, vector< pair<int, int>>, greater<pair<int, int>>> pq;vector<int> dist(G.V);initSSSP(s, dist);pq.push({ 0, s });while (!pq.empty()){int u = pq.top().second;pq.pop();for (auto e: G.adj[u]){int v = e.v;int w = e.weight;if (dist[u] != INT_MAX && dist[v] > dist[u] + w){dist[v] = dist[u] + w;pq.push({ dist[v], v });}}}// Print the shortest path distancesfor (int i = 0; i < G.V; ++i){cout << "Shortest path from " << s << " to " << i << " is " << dist[i] << endl;}}// Driver codeint main(){int V = 5;Graph G(V);G.addEdge(0, 1, 10);G.addEdge(0, 2, 5);G.addEdge(1, 2, 2);G.addEdge(1, 3, 1);G.addEdge(2, 1, 3);G.addEdge(2, 3, 9);G.addEdge(2, 4, 2);G.addEdge(3, 4, 4);G.addEdge(4, 3, 6);dijkstra(0, G);return 0;}
Explanation
-
Line 4: The
limits.h
header file is included to useINT_MAX
. -
Lines 8–13: The
struct Edge
has two data members,v
, which is the destination vertex, andweight
, which is the weight of the edge. -
Line 12: The constructor uses an initialization list to initialize the member variables, which is a cleaner and more efficient way of initializing member variables compared to using assignment statements in the constructor body. The colon (
:
) separates the initialization list from the constructor body. -
Lines 16–23: The constructor takes one parameter
V
and initializes theadj
vector with sizeV
. -
Lines 25–29: The
addEdge
function adds this edge to the adjacency list of vertexu
. -
Lines 32–36: The
initSSSP
function initializes all the distances toINT_MAX
, except the distance from the source vertex, which is set to0
. -
Line 41: The code declares a
priority_queue
data structure namedpq
. -
Line 44: The code initializes the priority queue
pq
with a pair of values {0
,s
}, wheres
is the source vertex. -
Lines 49–58: The
for
loop computes the shortest path distances from a given source vertex to all other vertices in the graph. It iterates over all adjacent vertices of the current vertexu
, updates the shortest distance to reach each of these adjacent verticesv
, if it can be improved by going throughu
, and adds the updatedv
with its new shortest distance to the priority queuepq
. -
Lines 72–81: The code initializes a directed graph with
5
vertices and adds weighted edges between them.
No negative edges
Dijkstra’s algorithm is particularly well-behaved when the input graph has no negative-weight edges. In this setting, the algorithm intuitively expands a wavefront outward from the source vertex , passing over vertices in increasing order of their distance from , similar to breadth-first search. The figure below shows the algorithm in action.
The images below show the first four iterations of Dijkstra’s algorithm on a graph with no negative edges. In each iteration, bold edges indicate predecessors; shaded vertices are in the priority queue; and the bold vertex is about to be scanned. The remaining iterations don’t change the distances or the shortest path tree.
We can derive a self-contained proof of correctness for Dijkstra’s algorithm in this setting by formalizing this wavefront intuition. For each integer , let denote the vertex returned by the th call to , and let be the value of just after this . In particular, we have and . We can’t assume at this point that the vertices ...