|
|archiveheader = {{talkarchivenav}}
|maxarchivesize = 70K
|counter = 12
|minthreadsleft = 4
|algo = old(365d)
|archive = Talk:Dijkstra's algorithm/Archive %(counter)d
}}
{{WikiProject banner shell|class=C|vital=yes|1=
{{WikiProjectBannerShell|1=
{{WikiProject Computer science|class=C |importance=top}}
{{mathsWikiProject rating|frequentlyviewed=yes|class=CMathematics|priority=Mid|field=discrete }}
{{WikiProject Computing|class=C |importance=High}}
}}
{{archives|auto=long|search=yes|bot=MiszaBot I|age=365}}
{{merged from|Uniform-cost search}}
== The explanation makes no sense ==
== Wrong anim? ==
Under Algorithm 2: <br>
"Assign to every node a distance from start value: for the starting node, it is zero, and for all other nodes, it is infinity, since initially no path is known to these nodes. During execution of the algorithm, the distance of a node N is the length of the shortest path discovered so far between the starting node and N.[17]" <br>
You just assigned INFINITE to ALL. How is the shortest going to be find? <br><br>
Under 3:<br>
"From the unvisited set, select the current node to be the one with the smallest finite distance; initially, this will be the starting node, which has distance zero. If the unvisited set is empty, or contains only nodes with infinite distance (which are unreachable)"<br>
Again, you assigned infinite to all nodes ... <br><br>
I stopped <spanreading style="fontit here. <!- size- Template: Unsigned smaller;"IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/ 50115. 12970. 8129. 162185| 50115. 12970. 8129. 162185]] ([[User talk: 50115. 12970. 8129. 162185#top|talk]]) 1408: 4049, 822 FebruaryOctober 20142024 (UTC)</ span><!-- Template:Unsigned IP --small> <!--Autosigned by SineBot--> ▼
Lnt-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contribuook 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? <span style="fotions/109.162.218.57|109.162.218.57]] ([[User talk:109.162.218.57|talk]]) 12:31, 7 April 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
== Add A Fact: "Dijkstra's algorithm proven universally optimal" ==
Read the algorithm, it keeps the minimum distance. [[Special:Contributions/129.67.95.240|129.67.95.240]] ([[User talk:129.67.95.240|talk]]) 13:03, 9 August 2011 (UTC)
I found a fact that might belong in this article. See the quote below
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? [[Special:Contributions/109.129.178.210|109.129.178.210]] ([[User talk:109.129.178.210|talk]]) 06:47, 28 April 2012 (UTC)
<blockquote>
Dijkstra’s algorithm was long thought to be the most efficient way to find a graph’s best routes. Researchers have now proved that it’s “universally optimal.”
</blockquote>
The fact comes from the following source:
: https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/
Here is a wikitext snippet to use as a reference:
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). <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/67.243.136.10|67.243.136.10]] ([[User talk:67.243.136.10|talk]]) 00:40, 15 June 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
<nowiki> {{Cite web |title=Computer Scientists Establish the Best Way to Traverse a Graph |url=https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/ |website=Quanta Magazine |date=2024-10-25 |access-date=2024-11-17 |language=en |first=Ben |last=Brubaker |quote=Dijkstra’s algorithm was long thought to be the most efficient way to find a graph’s best routes. Researchers have now proved that it’s “universally optimal.”}} </nowiki>
Perhaps it should also be noted in:
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) <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Tooto|Tooto]] ([[User talk:Tooto|talk]] • [[Special:Contributions/Tooto|contribs]]) </span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
https://en.wikipedia.org/wiki/Shortest_path_problem
This post was generated using the [[:meta:Future_Audiences/Experiment:Add_a_Fact|Add A Fact]] browser extension.
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. [[Special:Contributions/98.165.197.124|98.165.197.124]] ([[User talk:98.165.197.124|talk]]) 18:16, 10 August 2013 (UTC)
[[User:DKEdwards|DKEdwards]] ([[User talk:DKEdwards|talk]]) 18:37, 17 November 2024 (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? [[User:King rhoton|King rhoton]] ([[User talk:King rhoton|talk]]) 06:21, 2 February 2014 (UTC)
:What it actually means is that if
:#what you really want is the sorted order of vertices by distance from the source and not just the distances and paths,
:#you know ahead of time what graph you're going to run it on but not the weights, and
:#you can only access the weights by pairwise comparisons,
:then a specific version of Dijkstra (with a special priority queue) will get a number of comparisons within a constant factor of optimal. It's a nice result, and probably should be mentioned in this article ([[Dijkstra's algorithm]]) but I question the relevance to [[shortest path problem]] because it's about sorting rather than shortest paths per se. It may have been a bit oversold by Quanta. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 21:14, 17 November 2024 (UTC)
::[[User:Lfstevens]]: when adding this material, it would have been helpful for you to have read this thread. Your version of what they did is far too vague and hypey. I have edited it to more accurately reflect the claims of the new paper. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 08:01, 9 December 2024 (UTC)
:::Thanks for noticing and fixing my mush. It was pretty much a pull from the Quanta piece. [[User:Lfstevens|Lfstevens]] ([[User talk:Lfstevens|talk]]) 21:43, 9 December 2024 (UTC)
::::''Quanta'' is often mush. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 21:49, 9 December 2024 (UTC)
==Pseudocode==
When node 4 is reached from node 3, it shows, 22<11+9. Silly mistake i guess.
The pseudocode seems to fail into an endless loop unless all vertices are connected. [[User:Kkddkkdd|Kkddkkdd]] ([[User talk:Kkddkkdd|talk]]) 17:32, 23 November 2024 (UTC)
:The pseudocode removes a vertex from Q in every iteration, starting with all vertices. It cannot get into an endless loop. If the graph is not connected then some vertices will have priority infinity when they are removed, but that is not a problem for the algorithm. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:28, 24 November 2024 (UTC)
== Animation could be slightly improved ==
== Formatting of pseudocodes broken ==
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. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/67.183.182.104|67.183.182.104]] ([[User talk:67.183.182.104|talk]]) 03:24, 5 February 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
The change from @[[User:Lfstevens|Lfstevens]] on 8 December 2024, at 10:36 PM broke the formatting of the pseudocodes.<br>
== Animation for the colorblind ==
This also causes the pseudocode to be wrong since the nested loop is not recognizable (as nested) anymore.
Last good version:<br>
Holy cow, is that subtle red-green gradient not a good idea for colorblind people! <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/71.92.43.97|71.92.43.97]] ([[User talk:71.92.43.97|talk]]) 05:31, 13 January 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&oldid=1261954063 [[Special:Contributions/82.218.89.72|82.218.89.72]] ([[User talk:82.218.89.72|talk]]) 07:06, 16 December 2024 (UTC)
== An interesting paper questioning optimality ==
== This psudo code is hard to understand ==
This paper "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths":
https://arxiv.org/abs/2504.17033
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?
claims better-than-Dijkstra asymptotic performance in some edge cases.
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.
The abstract reads as follows: "We give a deterministic <math>O(m\log^{2/3}n)</math>-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the <math>O(m+n\log n)</math> time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP."
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.
They cite the earlier work on proof of universal optimality, and state that Dijkstra's algorithm is still optimal ''if you want to know the order of the points in the path''; their algorithm does not produce this ordering.
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).
It will be interesting to see if this gets out of pre-print status into [[WP:RS]].
▲ <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/50.129.81.162|50.129.81.162]] ([[User talk:50.129.81.162|talk]]) 14:40, 8 February 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
— [[User:The Anome|The Anome]] ([[User talk:The Anome|talk]]) 12:43, 1 June 2025 (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.--[[Special:Contributions/115.113.118.50|115.113.118.50]] ([[User talk: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. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/88.104.125.53|88.104.125.53]] ([[User talk:88.104.125.53|talk]]) 10:30, 12 April 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
| 