SingleSource ShortestPaths (Dijkstra Algorithm)
Updated:
1. Recall the basics

Unlike the BellmanFord algorithm where the edge weights can be negative, Dijkstra’s algorithm solves the singlesource shortestpaths problem on a weighted, directed graph $G = (V, E)$ for the case in which all edge weights are nonnegative.

The BellmanFord algorithm relaxes each edge $V  1$ times, whilst Dijkstra’s algorithm ( as well as the shortestpaths algorithm for directed acyclic graphs ) relax each edge exactly once.

With a good implementation, the running time of Dijkstra’s algorithm is generally lower than the BellanFord algorithm.

It is akin to the breadthfirst search in that set $S$ corresponds to the set of black vertices in a breadthfirst search; just as vertices in $S$ have their final shortestpath weights, so do black vertices in a breadthfirst search have their correct breadthfirst distances.

It is like Prim’s algorithm as both algorithms use a minpriority queue to find the “lightest” vertex outside a given set.

The loop invariant that Dijkstra’s algorithm maintains is $Q = V  S$

As mentioned above, Dijkstra’s algorithm always chooses the “lightest” or “closest” vertex in ${V  S}$ to add to set $S$, we say that it uses a greedy strategy.

Greedy strategies do not always yield optimal results in general, but as the following theorem and its corollary show, Dijkstra’s algorithm does indeed compute shortest paths.
2. Pseudocode
 the same preparation as before 
struct SSNode {
double d;
SSNode* π;
};
algorithm InitialLizeSingleSource(G, sourceNode):
For node in G do
node.d := +INF
node.π := NIL
sourceNode.d := 0
{ `Relaxation()` is nothing but examining whether or not
 by using the new "pit stop" (`u`) can reduce the price
 (`d`) of the node `v`.
}
algorithm Relax(u, v, (*CalcWeight)(_, _)):
if v.d > u.d + CalcWeight(u, v) then
v.d := u.d + CalcWeight(u, v)
v.π := u
algorithm Dijkstra(G, (*CalcWeight)(_, _), sourceNode):
InitialSingleSource(G, sourceNode)
DeterminedNodes := Ø
Q := new MinQueue(G.V, key=node.d)
While Q != Ø do
u := ExtractMin(Q)
DeterminedNodes += u
 obtain u's outgoing edges from u's adjacency list and relax them all 
For node in G.adj[u] do
Relax(u, node, CalcWeight)
3. Time Complexity
The running time of Dijkstra’s algorithm depends on how we implement the minpriority queue.

The outer whileloop has exactly $ \mid V \mid $ interations in which 2 MinQueue operations,
ExtractMin()
andInsert()
, are carried on; 
The inner forloop, where
DecreaseKey()
get called implicitly, iterates $ \mid E \mid $ times, since the total number of edges in all the adjacency lists is $ \mid E \mid $;
1) Use array: we maintain the minpriority queue by taking advantage of the vertices being numbered 1 to $ \mid V \mid $ and we simply store $v.d$ in the vth entry of an array. (similar to the directaddress hashing )
Insert()
andDecreaseKey()
: $O(1)$ timeExtractMin()
: $O(V)$ time (since we have to search through the entire array))
2) Use binary minheap: For the case where the graph is sufficiently sparse. ( the implementation should make sure that vertices and corresponding heap elements maintain handles to each other. )
ExtracMin()
andDecreaseKey()
: $O(lg V)$ timeBuildMinHeap()
: $O(V)$ time
3) Use Fibonacci heap: (see CRLS Chapter 19)
Leave a comment