4.4. Shortest paths in a graph

The Problem


–>Goal of the algorithm: Determine the shortest path from S to every other node in the graph.

Designing the algorithm-The Dijkstra algorithm


Dijkstra's algorithm(G,l)

Let S be the set of explored nodes
For each u in S, store the distance d(u)

Initially, S = {s} and d(s) = 0
While S ≠ V:

Select a node v ∉ S with at least one edge from S for which:
d'(v) = mine = (u,v):u in S d(u) + le is as small as possible
The formula above for d'(v) simply means that we choose a node v ∉ S that minimizes the path through S to u followed by the edge (u,v):

So, d'(v) = The shortest path from s to u + the cost of the edge (u,v)

Then add v to S and delete d(v) = d'(v)

EndWhile


Analyzing the algorithm




Implementations and Running Time

–> Better implementation:

First, explicitly maintain the values of the minima d'(v) for each v in V-S.

To improve efficiency, keep the nodes V-s in a priority Queue(PQ) with d'(v) as their keys.

The PQ will be useful when extracting the minimum(ExtractMin) and when Changing the key(changeKey).

So, to select a node to be added to S, use the ExtractMin operation of priority queues

To update a key d'(w) after adding v to S, we use the changeKey operation:
If a node w that remains in the PQ forms an edge e' =(v,w) in E with v:
Then, d'(w)= min(d'(w),d(v) + le'\\)

End if

The changeKey operation can occur at most once per edge, when the edge e' is added to S.

Thus using a PQ, Dijkstra's algorithm runs in: O(m) time +time for n ExtractMin and m changeKey operations
So, when the PQ is implemented using a heap, the overall running time is O(mlogn) since each operation then takes O(logn) time.


This section made a lot more sense especially since I read it after in-class discussion of the algorithm. I give it an 8/10.