|
This animation is simply terrible. From what I can tell, it's trying to depict the algorithm finding the shortest path between a (1) and b (5), and it comes up with 1,2,3,6,5 with a total length of 28. Clearly, the right answer to that question is 1,3,6,5 with a length of 20. I assume the order of turning vertices red is supposed to be the order of the path. On the other hand, if the algorithm is supposed to generate a shortest path tree, why does the animation not show any branching? [[User:King rhoton|King rhoton]] ([[User talk:King rhoton|talk]]) 06:21, 2 February 2014 (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)
:It's not wrong: when node 4's distance changes that is the 'tentative distance' mentioned in step 3 changing. At that point node 4 is not the current node, node 3 is. 4 is being checked as a neighbor of the current node at 3.
:The all nodes termination is fine, too. Dijkstra's algorithm finds the minimal distance between a particular node and all other nodes in the graph (not a single destination), so it's obviously never going to terminate when run against an infinite graph. You need some variant of Dijkstra (such as [[A*_search_algorithm|A*]] to handle infinite graphs. - [[User:MrOllie|MrOllie]] ([[User talk:MrOllie|talk]]) 14:58, 9 August 2011 (UTC)
For me, the confusing steps are 2 and 3. On step 2, you mark all nodes as ''unvisited'' and next, on step 3, you add all neighbors of current node to the ''unvisited set''. Firstly, is there a reason for the unvisited-mark when having a visited-mark? Secondly, maybe the ''unvisited set'' is also unnecessary (as it just binds useful space), because the nodes belonging to this set are those who have distance less than infinity and are not marked as visited. [[User:Vevek|Vevek]] ([[User talk:Vevek|talk]]) 23:28, 15 August 2011 (UTC)
I would suggest to change line 3 in the code for getting the shortest path to:
1 ''S'' := empty sequence
2 ''u'' := ''target''
3 '''while''' ''u'' is defined:
4 insert ''u'' at the beginning of ''S''
5 ''u'' := previous[''u'']
6 '''end while''' ;
This way, you also get the start node. This is not the case in the current version. [[User:Milcke|Milcke]] ([[User talk:Milcke|talk]]) 17:06, 8 October 2011 (UTC)
So the "unvisited set" is not the set of nodes marked as unvisited?
That's very confusing. Also, in step 4 we are told to remove the current node from the "unvisited set." But if the current node is the initial node, it isn't in the "unvisited set". <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/66.188.89.180|66.188.89.180]] ([[User talk:66.188.89.180|talk]]) 22:11, 4 November 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
===Just implemented the pseudocode for [http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Python Rosetta Code] and found these issues===
Action decrease-key v in Q at line 24 should be omitted if Q is a set as stated in line 9. The wp back-tracking pseudocode also misses a final insert of u at the beginning of S that must occur after exiting the while loop. --[[User:Paddy3118|Paddy]] ([[User talk:Paddy3118|talk]]) 21:12, 21 December 2012 (UTC)
== decrease-key v in Q; ==
Why is this line here? decrease-key was never explained. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Eliotistic|Eliotistic]] ([[User talk:Eliotistic|talk]] • [[Special:Contributions/Eliotistic|contribs]]) 04:37, 15 January 2013 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
== Animation could be slightly improved ==
| 