Content deleted Content added
→Algorithm: new section |
|||
Line 86:
::<math>|V| \cdot \mathtt{deletemin} + (|V| + |E|) \cdot \mathtt{decreasekey}</math>
: where the running time for decreasekey is the same as for insert key. This becomes important in explaining some of the running times. Please, someone, verify that I have got this correctly and update appropriately if there is a mistake in the article. [[User:Superpronker|Superpronker]] ([[User talk:Superpronker|talk]]) 14:03, 7 June 2011 (UTC)
== Algorithm ==
Step four of the algorithm is confusing. In its language it states that a visited nodes minimum distance will never be changed. This, is wrong as when the current node its switched a new minimum distance is calculated - keeping the distance that is minimum.
This is seen in the animation, where node 4 changes it value from 22 to 22 from steps 2 to 3.
Additionally, the end condition that 'all nodes' have been visited seems tenous, suppose an infinite undirected graph with two identified points (a,b), this would have infite computational time. The pseudocode on this page seems to address - can we make this less ambiguous? [[Special:Contributions/129.67.95.240|129.67.95.240]] ([[User talk:129.67.95.240|talk]]) 13:10, 9 August 2011 (UTC)
| |||