Dijkstra’s Algorithm
– to find Single Source Shortest Paths
Some useful definitions:
• Shortest Path Problem: Given a connected directed graph G with non-negative weights on the edges and a root vertex r, find for each vertex x, a directed path P (x) from r to x so that the sum of the weights on the edges in the path P (x) is as small as possible.
Algorithm
• By Dutch computer scientist Edsger Dijkstra in 1959.
• Solves the single-source shortest path problem for a graph with nonnegative edge weights.
• This algorithm is often used in routing.
E.g : Dijkstra’s algorithm is usually the working principle behind link-state routing protocols
ALGORITHM Dijkstra(G, s)
//Input: Weighted connected graph G and source vertex s
//Output: The length Dv of a shortest path from s to v and its penultimate vertex Pv for every vertex v in V
//initialize vertex priority in the priority queue Initialize (Q)
for every vertex v in V do
The method
Dijkstra’s algorithm solves the single source shortest path problem in 2 stages.
Stage 1: A greedy algorithm computes the shortest distance from source to all other nodes in the graph and saves in a data structure.
Stage 2 : Uses the data structure for finding a shortest path from source to any vertex v.
-
At each step, and for each vertex x, keep track of a “distance” D(x) and a directed path P(x) from root to vertex x of length D(x).
-
Scan first from the root and take initial paths P( r, x ) = ( r, x ) with D(x) = w( rx ) when rx is an edge, D(x) = ∞ when rx is not an edge.
For each temporary vertex y distinct from x, set
D(y) = min{ D(y), D(x) + w(xy) }
Example:
Apply Dijkstra’s algorithm to find Single source shortest paths with vertex a as the source.
Solution:
Length Dv of shortest path from source (s) to other vertices v and Penultimate vertex Pv for every vertex v in V:
Conclusion:
• Doesn’t work with negative weights
• Applicable to both undirected and directed graphs
• Use unordered array to store the priority queue: Efficiency = Θ(n2)
• Use min-heap to store the priority queue: Efficiency = O(m log n)