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. |
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)
The Triangle formed by node 1,3 and 6 has wrong length for the line connecting 1 and 6.For a triangle inequality to hold it can't be (14) larger than other two sides length (9+2). — Preceding unsigned comment added by 67.243.136.10 (talk) 00:40, 15 June 2013 (UTC)
Generally the numbers do not represent geometric length, they represent some kind of cost, for example, it could be the travel time between nodes. The 14 could then represent the fact that a farm track takes 14 mins, while the main road only takes 9 + 2 mins down a side street. --tooto 16:03, 24 July 2013 (UTC) — Preceding unsigned comment added by Tooto (talk • contribs)
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)
Just implemented the pseudocode for 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. --Paddy (talk) 21:12, 21 December 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)
Syntax higlight
I've modified the pseudocode in my sandbox to make it use syntax highlight. I think the language it resembles the most is Fortran, but maybe is not the case. Do you think that this makes it more understandable? http://en.wikipedia.org/wiki/User:WLoku/sandbox — Preceding unsigned comment added by WLoku (talk • contribs) 14:52, 9 November 2012 (UTC)
- I prefer boldfaced keywords over the pale yellowish colour. The automatic syntax highlight isn't correct either (e.g. the "for each" isn't highlighted). —Ruud 23:00, 9 November 2012 (UTC)
decrease-key v in Q;
Why is this line here? decrease-key was never explained. — Preceding unsigned comment added by Eliotistic (talk • contribs) 04:37, 15 January 2013 (UTC)
Animation could be slightly improved
I don't understand why an otherwise awesome animation takes a lame shortcut at the end with the "That's all" text. The algorithm doesn't take any such shortcut so it just hurts one's understanding to do this. The animation should highlight node 4 as grey then draw an arrow towards node 5 where it decides that the current value is already the best (so does not update) similar to when node 2 evaluates node 3. Then node 4 should turn red as did the others. Once all nodes are red (except maybe 5 for obvious reasons), it helps to visualize that execution is complete. — Preceding unsigned comment added by 67.183.182.104 (talk) 03:24, 5 February 2013 (UTC)