Dijkstra’s Algorithm - to find Single Source Shortest Paths.

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 = Θ(n²)

• Use min-heap to store the priority queue: Efficiency = O(m log n)