Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision |
courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioniv [2012/02/29 07:02] – mugabej | courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioniv [2012/02/29 07:28] (current) – mugabej |
---|
--> 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.\\ |