Shortest Path Problem

Given a connected graph G=(V,E), a weight d:E R+ and a fixed vertex s in V, find a shortest path from s to each vertex v in V.

Dijkstra’s Algorithm:

Dijkstra’s algorithm is known to be a good algorithm to find a shortest path.

1.    Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then stop, otherwise go to step 2.
2.    For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
3.    Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
4.    Let Si+1 = Si cup {ui+1}.
5.    Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.
The time required by Dijkstra’s algorithm is O(|V|2). It will be reduced to O(|E|log|V|) if heap is used to keep {v in V\Si : L(v) < infinity}.