Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 10:49, 9 January 2020

Latest revision as of 12:57, 1 June 2025

(64 intermediate revisions by 24 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}}

{{Vital article|class=C|topic=Mathematics|level=5}}

}}

{{archives|auto=long|search=yes|bot=MiszaBot I|age=365}}

{{merged from|Uniform-cost search}}

== The explanation makes no sense ==

== Terminological Dissonance? ==

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 reading it here. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/115.70.29.185|115.70.29.185]] ([[User talk:115.70.29.185#top|talk]]) 08:49, 22 October 2024 (UTC)</small> <!--Autosigned by SineBot-->

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

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

== Complexity with Fibonacci heaps ==

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

A few users have been changing the complexity with Fibonacci heaps from <math>O(|E| + |V| \log|V|)</math> to <math>O((|E| + |V|) \log|V|)</math> without any justification. The former appears to be correct based on the reasoning in the article:

<blockquote>

:For any implementation of the vertex set {{mvar|Q}}, the running time is in

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

::<math>O(|E| \cdot T_\mathrm{dk} + |V| \cdot T_\mathrm{em})</math>,

</blockquote>

:where <math>T_\mathrm{dk}</math> and <math>T_\mathrm{em}</math> are the complexities of the ''decrease-key'' and ''extract-minimum'' operations in {{mvar|Q}}, respectively.

The fact comes from the following source:

since <math>T_\mathrm{dk} = \Theta(1)</math> for Fibonacci heaps.

: https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/

Hence I am reverting the complexity with Fibonacci heaps back to <math>O(|E| + |V| \log|V|)</math>. -- [[User:Paddu|Paddu]] ([[User talk:Paddu|talk]]) 15:44, 27 December 2017 (UTC)

Here is a wikitext snippet to use as a reference:

== Is the algorithm description incorrect? ==

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

Step six of the algorithm section is:

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.

"6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3."

[[User:BotlordDKEdwards|BotlordDKEdwards]] ([[User talk:BotlordDKEdwards|talk]]) 0618:0437, 2117 FebruaryNovember 20182024 (UTC)

I don't believe that's correct. Shouldn't the "tentative" be removed? Since this is an important article I wanted to be sure I was correct before editing it, but if it is incorrect [https://www.youtube.com/watch?v=gdmfOwyQlcI&t=20s we've already hit citogenesis].

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

[[User:Botlord|Botlord]] ([[User talk:Botlord|talk]]) 06:04, 21 February 2018 (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 Itpseudocode isremoves thea smallestvertex amongfrom allQ thein "tentativeevery distances".iteration, starting Whilewith itall isvertices. trueIt thatcannot forget theinto nodean withendless theloop. smallestIf one,the itgraph is alsonot theconnected realthen distance,some itvertices iswill probablyhave notpriority soinfinity forwhen thethey are othersremoved, and even forbut that oneis it requiresnot a proof,problem which will only be given afterfor the algorithm has been described. --—[[User:AlexeyDavid MuranovEppstein|AlexeyDavid MuranovEppstein]] ([[User talk:AlexeyDavid MuranovEppstein|talk]]) 0617:2528, 2124 FebruaryNovember 20182024 (UTC)

== Formatting of pseudocodes broken ==

== Is there a typo in the "Invariant hyphothesis" sentence? ==

It says: "This assumption is only considered if a path not exists," but should it be "This assumption is only considered if a path exists," ?

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

== Animation incorrect/misleading? ==

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

Last good version:<br>

The main animation is very confusing. It purports to minimize distance, but in the triangle formed by nodes 1-3-6, the distance between nodes 1 and 6 is labelled as 14, while the distance from node 1 to 3 to 6 sums to 11, which is geometrically imnpossible by the nature of triangles. Visually, the path 1-6-5 is obviously the shortest distance. Either the labels of the distances between nodes should be changed (and therefore the optimal path changed) or the description should be changed to not refer to distance and make clear that the labels do not reference distance between nodes. Am I seeing this correctly? [[User:Voyaging|<span style="color:darkblue">'''''Voyaging'''''</span>]][[User talk:Voyaging|^{<span style="color:darkred">'''talk'''</span>}]] 14:44, 11 July 2019 (UTC)

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

== Practical optimizations and infinite graphs ==

This paper "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths":

https://arxiv.org/abs/2504.17033

The pseudocode is a sort of Breadth-First Search, not Uniform-Cost Search, as it does not consider edge weight.[[User:Ehasl|Elias]] ([[User talk:Ehasl|talk]]) 10:49, 9 January 2020 (UTC)

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)