====== 4.4. Shortest paths in a graph ======

=== The Problem ===

  * 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<sub>e</sub>//≥ 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.
\\
===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) = min<sub>e = (u,v):u in S </sub>d(u) + //l//<sub>e</sub> 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 ===

  * For each u in S, the path P<sub>u</sub> 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
\\
=== Implementations and Running Time ===

  * 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//<sub>e'</sub>\\)
>>>>>>>>>>>>>>>>>>>>>>>>>> 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.