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?
Lnt-size: smaller;" class="autosigned">—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)
Shouldn't the animation end with an identification of the selected path? All it does is flash up "20(4) >= 20(5), That's All". Shouldn't it mark the path from A to B (1, 3, 6, 5)? As it stands now, the animation ends with 4 red circles and no clear indication of what was actually accomplished. Additionally, why are circles marked red then labeled OUT? The OUT is confusing. This indicates to me that the vertex is "out" of the path, which is not the case. It's also inconsistent because vertex #6 is not marked out even though it is colored red. 98.165.197.124 (talk) 18:16, 10 August 2013 (UTC)
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? King rhoton (talk) 06:21, 2 February 2014 (UTC)
When node 4 is reached from node 3, it shows, 22<11+9. Silly mistake i guess.
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)
Animation for the colorblind
Holy cow, is that subtle red-green gradient not a good idea for colorblind people! — Preceding unsigned comment added by 71.92.43.97 (talk) 05:31, 13 January 2014 (UTC)
This psudo code is hard to understand
There is 'no language' for psudo code, but whatever language this psudo-code is closest to is hard for me (and probably others) to understand. Colon-Equal Sign? What does that mean?
Can someone who understands this Psudo-code break it down further? Make it closer to plain English? Don't assume the reader understands the symbols being used in the psudo code please.
There are many different computer languages out there: C/C++, C#, Lua, Lisp, Visual Basic, Quick Basic, Delphi, and many more. Why should someone who writes code in Visual Basic not be able to understand the algorithm on Wikipedia? Why should they have to learn Lisp to be able to decipher the meaning of "psudo-code" to understand and learn something here? It could take someone years to learn another language, if they even have access to the tools/information to learn that other language.
Psudo-code on Wikipedia should probably be written so that someone who doesn't know any programming languages at all can understand it. After all, programming is math. Why should someone have to understand a specific programming language or shorthand to understand an algorithm? Psudo-code on Wikipedia should be universal, or at least understood in the language the page is written in (English and Math for example).
— Preceding unsigned comment added by 50.129.81.162 (talk) 14:40, 8 February 2014 (UTC)
Wrong pseudo-code
The pseudo code mentions this:
24 decrease-key v in Q; // Reorder v in the Queue
Then it mentions the same thing in the separate discussion of priority queue implementation:
19 PQ.decrease_priority(v,alt)
Obviously, the first mention is wrong and the pseudo-code is, instead of talking about a normal queue, talking about the the same thing as priority queue section. I can make the change but I think more knowledgeable person ought to do it.--115.113.118.50 (talk) 07:12, 18 March 2014 (UTC)
Relaxation condition?
The article starts talking about the "relaxation condition" without defining it; I don't think this is very clear but I don't feel confident about editing it. http://stackoverflow.com/questions/2592769/what-is-the-relaxation-condition-in-graph-theory sort of explains (external link) but I can't find a decent definition within Wikipedia. — Preceding unsigned comment added by 88.104.125.53 (talk) 10:30, 12 April 2014 (UTC)
Cleaning up inconsistencies
I've tried to (begin to) address a few issues with this page that have been previously mentioned. Namely:
- The first algorithm referred to a set, but then used priority queue operations on the set. A separate priority queue algorithm was then introduced. Either there should only be a single algorithm, or the first, simpler algorithm should stick to using a set
- The algorithms referred to 'relaxing' edges without defining what this is or linking to a definition
- The algorithms were inconsistent with each other, i.e. they did the same initialization in different ways. There were odd semicolons after some lines in the first algorithm, not the second.
I think there are larger issues with individual pages that use graphs being inconsistent with each other, and with the main Graph article itself. It would be nice if we could come up with a standard way of describing graphs and graphing algorithms, but these are bigger issues that will take a lot more work to address. --Peasaep (talk) 06:44, 25 May 2014 (UTC)
Proposed merge with Uniform-cost search
A look at Dijkstra's 1959 paper reveals that what he was describing is actually closer to what Russell and Norvig call UCS than the algorithm described in this page. The term UCS pops up in literature sometimes, but is equated with Dijkstra's algorithm by, e.g., Korf and Zhang, Klein and Manning. See Talk:A* search algorithm#Relation to uniform-cost search for a longer discussion about when an algorithm deserves to be called Dijkstra's.
Ping Kri, David Eppstein. QVVERTYVS (hm?) 10:36, 7 November 2014 (UTC)