Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioniv [2012/02/29 01:31] – created mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioniv [2012/02/29 07:28] (current) – mugabej
@@ Line 8: / Line 8: @@
 \\
 -->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.