Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 15:20, 17 September 2017

Latest revision as of 12:57, 1 June 2025

(75 intermediate revisions by 32 users not shown)

Line 8:

|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}}

{{Maths rating |frequentlyviewed=yes |class=CWikiProject Mathematics|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}}

== AnyThe videoexplanation ofmakes animationno available?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>

[1]:I stopped http://rosettacodereading it here.org/wiki/Dijkstra's_algorithm#Java <small!-- Template:Unsigned IP --><spansmall class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[UserSpecial:CkorakidisContributions/115.70.29.185|Ckorakidis115.70.29.185]] ([[User talk:Ckorakidis115.70.29.185#top|talk]] • [[Special:Contributions/Ckorakidis|contribs]]) 1908:3149, 1722 October 20152024 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

That animation is killing me. I so much want to carefully look at it's calculations, but they flash up there for just a half second. It is maddening.

== Add A Fact: "Dijkstra's algorithm proven universally optimal" ==

[https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#/media/File:Dijkstra_Animation.gif That animation] does not work as described. The calculated cost as shown in the animation is 20, while the correct one based on the described procedure is 28 (or 26 if bidirectional [1])

[1]: http://rosettacode.org/wiki/Dijkstra's_algorithm#Java <small><span class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Ckorakidis|Ckorakidis]] ([[User talk:Ckorakidis|talk]] • [[Special:Contributions/Ckorakidis|contribs]]) 19:31, 17 October 2015 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

I found a fact that might belong in this article. See the quote below

<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:

== Terminological Dissonance? ==

<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:

The terminology in the caption for the animation is not in full agreement with the description of the algorithm: (a) the algorithm description does not mention a "tentative set" - it does mention "tentative distances", and it mentions an "unvisited set"; (b) the algorithm description mentions no "heuristic", but the caption to the animation says that the algorithm uses a "heuristic that is identically zero". At first it seemed to me that the caption of the animation intended "tentative set" to mean that which is meant by "unvisited set" in the algorithm description, but as I thought about it, I am unsure; on the other hand, it seems clear to me that even if that is not the intent of the caption, it '''does''' follow that the "tentative set" is identical to the "unvisited set" in that example. Matt Insall 13:15, 5 August 2017 (UTC) <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Espresso-hound|Espresso-hound]] ([[User talk:Espresso-hound#top|talk]] • [[Special:Contributions/Espresso-hound|contribs]]) </small> <!--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.

== Description section of artice ==

In the second paragraph after the note, it says "This is done by determining the sum of the distance between an unvisited intersection and the value of the current intersection". There should be two intersections following between, but there is only one intersection since value is not an intersection.

--[[User:JackrepenningDKEdwards|JackrepenningDKEdwards]] ([[User talk:JackrepenningDKEdwards|talk]]) 18:5437, 2417 SeptemberNovember 20162024 (UTC)

The phrase, "This is done by determining the sum of the distance between an unvisited intersection and the value of the current intersection" should be changed to read, "This is done by adding the value of the current intersection to the distance between the current intersection and an unvisited intersection". [[User:RHB100|RHB100]] ([[User talk:RHB100|talk]]) 00:34, 12 January 2016 (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==

== Pronunciation of the inventor's name ==

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)

Could we add the correct phonetical expression for the inventors name? Anyone researching for this topic will have trouble to pronounce the name correctly. <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2A02:8109:80C0:7EC:E8F6:F2B8:8896:A526|2A02:8109:80C0:7EC:E8F6:F2B8:8896:A526]] ([[User talk:2A02:8109:80C0:7EC:E8F6:F2B8:8896:A526|talk]]) 10:33, 22 April 2016 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

: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)

== Description: "Pencil arrows" vs. "parents" ==

A paragraph in the Description advises "in pencil, mark the road with an arrow pointing to the relabeled intersection." The next paragraph talks about a visited node's "parent." I think these are talking about the same thing, but it's not very clear. Perhaps better wording might be "by following the nodes' parents ''(that is, traversing the arrows backward)''", or perhaps in the first paragraph, "mark the road with an arrow pointing to the relabeled intersection ''(from 'parent' to 'child')''"

== Formatting of pseudocodes broken ==

--[[User:Jackrepenning|Jackrepenning]] ([[User talk:Jackrepenning|talk]]) 18:54, 24 September 2016 (UTC)

The change from @[[User:Lfstevens|Lfstevens]] on 8 December 2024, at 10:36 PM broke the formatting of the pseudocodes.<br>

This also causes the pseudocode to be wrong since the nested loop is not recognizable (as nested) anymore.

Last good version:<br>

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 paper "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths":

https://arxiv.org/abs/2504.17033

claims better-than-Dijkstra asymptotic performance in some edge cases.

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."

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]].

&mdash; [[User:The Anome|The Anome]] ([[User talk:The Anome|talk]]) 12:43, 1 June 2025 (UTC)