| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioniv [2012/02/29 03:28] – 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\\ |
| --> Better implementation: | --> Better implementation: |
| >>>>>>>>>> First, explicitly maintain the values of the minima d'(v) for each v in V-S.\\ | >>>>>>>>>> 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. \\ | >>>>>>>>>> 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).\\ | >>>>>>>>>> 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\\ | >>>>>>>>>> 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: | >>>>>>>>>> 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: | >>>>>>>>>>>>>>>>>>>>>>>>>> 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>\\ | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Then, d'(w)= min(d'(w),d(v) + //l//<sub>e'</sub>\\) |
| >>>>>>>>>>>>>>>>>>>>>>>>>> End if | >>>>>>>>>>>>>>>>>>>>>>>>>> End if |
| >>>>>>>>>> The changeKey operation can occur at **most once per edge**, when the edge e' is added to S.\\ | >>>>>>>>>> The changeKey operation can occur at **most once per edge**, when the edge e' is added to S.\\ |
