4.4. Shortest paths in a graph

• We are given a directed graph G = (V,E) with a starting node S.We assume that s has a path to every other node in G.
• Each edge e has a length l_e≥ 0, which it the cost of traversing e.
• For each path P, the length of P(l(P)) = ∑ of all edges in P.
  

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

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) = min_{e = (u,v):u in S} d(u) + l_e 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

• For each u in S, the path P_u is the shortest s-u path.(Proof:Book)
• The basic idea of the proof is that Dijkstra's algorithm selects the shortest path at each iteration.

• Remarks:
  • Dijkstra's algorithm is used only for non negative costs of edges:The proof simply fails when calculating d'(v).
  • Dijkstra's algorithm is simple and is a continuation of the Breadth-First Search algorithm

• There are n-1 iterations of the while loop for a graph with n nodes
• First attempt at selecting the correct node v efficiently:
  • Consider each node v ∉ S
  • Go through all of the edges between S and v to find the one that satisfies the equation for d'(v)and select it
  • For a graph with m edges, the whole operation takes O(mn) time since computing all the minima takes O(m) 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) + l_e'\\)

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.