|
|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}}
== MostThe Commonexplanation Implementationmakes no sense ==
==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>
Reply: Am I thestopped only one who findsreading it ahere. little ironic<!-- thatTemplate:Unsigned theIP pseudo- code clearly has a "goto" in the last line? ->< span style="font-size: smaller;"small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/ 99115. 11870. 18929. 11185| 99115. 11870. 18929. 11185]] ([[User talk: 99115. 11870. 18929. 11185#top|talk]]) 1408: 1449, 2022 MarchOctober 20122024 (UTC)</ span><!-- Template:Unsigned IP --small> <!--Autosigned by SineBot--> ▼
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. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/66.31.200.86|66.31.200.86]] ([[User talk:66.31.200.86|talk]]) 06:25, 18 February 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
== Add A Fact: "Dijkstra's algorithm proven universally optimal" ==
== Pretty muddy ==
I found a fact that might belong in this article. See the quote below
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. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/64.134.224.50|64.134.224.50]] ([[User talk:64.134.224.50|talk]]) 00:50, 21 March 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
<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:
Reply:
<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>
Well actually you set the root to 0, so that will be smaller than infinity, then you set its neighbors and so on... <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/70.42.29.3|70.42.29.3]] ([[User talk:70.42.29.3|talk]]) 20:53, 4 May 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
Perhaps it should also be noted in:
▲Reply: Am I the only one who finds it a little ironic that the pseudo-code clearly has a "goto" in the last line? <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/99.118.189.11|99.118.189.11]] ([[User talk:99.118.189.11|talk]]) 14:14, 20 March 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--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.
== Wrong anim? ==
[[User:DKEdwards|DKEdwards]] ([[User talk:DKEdwards|talk]]) 18:37, 17 November 2024 (UTC)
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? <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/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-->
: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==
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)
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)
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)
== Formatting of pseudocodes broken ==
The change from @[[User:Lfstevens|Lfstevens]] on 8 December 2024, at 10:36 PM broke the formatting of the pseudocodes.<br>
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 also causes the pseudocode to be wrong since the nested loop is not recognizable (as nested) anymore.
Last good version:<br>
This is seen in the animation, where node 4 changes it value from 22 to 22 from steps 2 to 3.
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 ==
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)
This paper "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths":
: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)
https://arxiv.org/abs/2504.17033
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)
claims better-than-Dijkstra asymptotic performance in some edge cases.
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)
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."
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-->
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.
It will be interesting to see if this gets out of pre-print status into [[WP:RS]].
===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)
— [[User:The Anome|The Anome]] ([[User talk:The Anome|talk]]) 12:43, 1 June 2025 (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]:".[[User:Glen Koundry|Glen Koundry]] ([[User talk: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 <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:WLoku|WLoku]] ([[User talk:WLoku|talk]] • [[Special:Contributions/WLoku|contribs]]) 14:52, 9 November 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
: 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). —''[[User:Ruud Koot|Ruud]]'' 23:00, 9 November 2012 (UTC)
| 