Talk:Dijkstra's algorithm
| This is the talk page for discussing improvements to the Dijkstra's algorithm article. This is not a forum for general discussion of the subject of the article. |
Article policies
|
| Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1, 2Auto-archiving period: 12 months  |
 | This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||||||||||||||||||
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
| |||||||||||||||||||||||||||||||||||||||||||||||
|
||
|
This page has archives. Sections older than 365 days may be auto-archived by Lowercase sigmabot III if there are more than 4. |
Most Common Implementation
the article formerly had an unsourced implication that the most common implementation of Dijkstra uses a Fibonacci heap. I'm pretty sure that's wrong, but I can't find a good source for the most common implementation. — Preceding unsigned comment added by 66.31.200.86 (talk) 06:25, 18 February 2012 (UTC)
Pretty muddy
if you try to take the psudocode and directly turn it into code. Well by 5 lines an it fails. set all distance to infinity. Then you check to see if edge distance is infinity? ofc it was, you just set it to that, and now you exit. —Preceding unsigned comment added by 64.134.224.50 (talk) 00:50, 21 March 2011 (UTC)
Reply: Well actually you set the root to 0, so that will be smaller than infinity, then you set its neighbors and so on... —Preceding unsigned comment added by 70.42.29.3 (talk) 20:53, 4 May 2011 (UTC)
Reply: Am I the only one who finds it a little ironic that the pseudo-code clearly has a "goto" in the last line? — Preceding unsigned comment added by 99.118.189.11 (talk) 14:14, 20 March 2012 (UTC)
Wrong anim?
Look at the anim. First it goes to node #2. then when it wants to go to node #3 it count the length 9. it's absolutely wrong because if you want to go from #2 to #3 you must pass from a edge length 10. So what's the meaning of this? can anyone explain it for me? —Preceding unsigned comment added by 109.162.218.57 (talk) 12:31, 7 April 2011 (UTC)
Read the algorithm, it keeps the minimum distance. 129.67.95.240 (talk) 13:03, 9 August 2011 (UTC)
I think I spotted another error: when an arrow is drawn from node #3 to node #4, a question mark and subsequently " 22 < 11 + 9 " is written above node #4. Shouldn't the inequality sign be the other way? 109.129.178.210 (talk) 06:47, 28 April 2012 (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? 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* to handle infinite graphs. - 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. 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. 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". — Preceding unsigned comment added by 66.188.89.180 (talk) 22:11, 4 November 2012 (UTC)
Finding multiple shortest paths
In order to find all shortest paths between two nodes, I believe that the "if alt < dist[v]:" should be changed to "if alt <= dist[v]:".Glen Koundry (talk) 13:59, 6 November 2012 (UTC)