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