| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioniv [2012/02/29 01:55] – mugabej | courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioniv [2012/02/29 07:28] (current) – mugabej |
|---|
| >>>>>>>>>>>>>> While S ≠ V: | >>>>>>>>>>>>>> While S ≠ V: |
| >>>>>>>>>>>>>>>>>>>>>>> Select a node v ∉ S with at least one edge from S for which: | >>>>>>>>>>>>>>>>>>>>>>> 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> + //l//<sub>e</sub> is as small as possible | >>>>>>>>>>>>>>>>>>>>>>> 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) | >>>>>>>>>>>>>>>>>>>>>>> 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) | >>>>>>>>>>>>>>>>>>>>>>> Then add v to S and delete d(v) = d'(v) |
| >>>>>>>>>>>>>>> EndWhile | >>>>>>>>>>>>>>> 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. |
