Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioniv [2012/02/29 07:02] mugabejcourses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioniv [2012/02/29 07:28] (current) mugabej
Line 44: Line 44:
 --> 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-in a priority Queue(PQ) with d'(v) as their keys. \\+>>>>>>>>>> To improve efficiency, keep the nodes V-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.\\
courses/cs211/winter2012/journals/jeanpaul/chapterfour_sectioniv.1330498949.txt.gz · Last modified: 2012/02/29 07:02 by mugabej
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0