Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 05:01, 12 October 2022

Latest revision as of 12:57, 1 June 2025

(49 intermediate revisions by 15 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 ==

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

Under Algorithm 2: <br>

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," ?

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

== Dubious ==

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

In the section "Using a priority queue", we have:

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

:Yet another alternative is to add nodes unconditionally to the priority queue and to instead check after extraction that no shorter connection was found yet. This can be done by additionally extracting the associated priority p from the queue and only processing further '''if p ≤ dist[u]''' inside the while Q is not empty loop.

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

https://cs.stackexchange.com/a/118406/ thinks that this is mistaken and should be replaced with '''p = dist[u]'''. Ryoji writes (CC-BY SA 4.0):

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

:You are right. Checking k < d[u] is not sufficient and updating d[u] on the next line is not necessary.

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.

:The check prevents proceeding when the source is picked up from the queue (then k = 0 and d[s] = 0). Also, d[u] (u is fixed) is monotonically decreasing as loop proceeds, so even though it is updated after (u, d[u]) is put on the queue, k >= d[u] holds when (u,k) is picked up from the queue. Moreover, if d[u] is strictly smaller than k , the element should simply be ignored since it cannot be the shortest path to u.

[[User:DKEdwards|DKEdwards]] ([[User talk:DKEdwards|talk]]) 18:37, 17 November 2024 (UTC)

:You can change the condition to k == d[u] and remove following update to d[u].

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

Should we replace the condition with k == d[u]? —[[User:Enervation|Enervation]] ([[User talk:Enervation|talk]]) 16:44, 30 December 2020 (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)

== Roads and intersections ==

== Formatting of pseudocodes broken ==

Article says that "Note: For ease of understanding, this discussion uses the terms intersection, road and map – however, in formal terminology these terms are vertex, edge and graph, respectively."

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

This...doesn't make it easier. It actually sounds incredibly patronizing. Who in the right mind would try to learn Dijkstra's algorithm without knowing what a vertex is? [[Special:Contributions/2001:569:57B2:4D00:71E1:A843:C41:841C|2001:569:57B2:4D00:71E1:A843:C41:841C]] ([[User talk:2001:569:57B2:4D00:71E1:A843:C41:841C|talk]]) 16:22, 25 May 2022 (UTC)

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

Last good version:<br>

== Pseudocode improvement ==

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

In first pseudocode block, on line 15, dist[u] is checked for not being INFINITY. But if it is INFINITY at this point, the code will continue useless looping, because all remaining vertices will also have dist[u]=INFINITY and not influence the result. Maybe move the INFINITY check to line 11 and break out of while block, it would be more human readable too I think --[[User:Shrddr|Shrddr]] ([[User talk:Shrddr|talk]]) 20:44, 20 August 2022 (UTC)

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

https://arxiv.org/abs/2504.17033

We should stick to sources rather than commit [[WP:OR]]. CLRS has

<pre>

DIJKSTRA(G, w, s) // Graph G, weights w, source vertex s

1 INITIALIZE-SINGLE-SOURCE(G, s) // lines 3-5 of our algorithm

2 S = 0 // empty set

3 Q = G.V // line 6

4 while Q non empty

5 u = EXTRACT-MIN(Q) // line 10, 11

6 S = S union {u}

7 for each vertex v in G:Adj(u) // slightly different to ours

8 RELAX(u,v,w)

</pre>

where RELAX is

<pre>

RELAX(u, v, w)

1 if v.dist > u.dist + w(u, v)

2 v.dist = u.dist + w(u, v)

3 v.prev = u

</pre>

There is nothing in this algorithm with a test of u.dist being infinity. So I think its safe to remove the condition entirely. --[[User:Salix alba|Salix alba]] ([[User talk:Salix alba|talk]]): 10:44, 21 August 2022 (UTC)

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

:The text before pseudocode box ends with reference to https://doi.org/10.1007%2F978-3-540-77978-0 which does mention infinity check (see "algorithm" at page 197). But then for some reason it's left out in "pseudocode" at page 198. [[User:Shrddr|Shrddr]] ([[User talk:Shrddr|talk]]) 12:51, 21 August 2022 (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."

== Pseudocode is wrong ==

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.

The pseudocode that uses a priority queue is plain wrong, it produces garbage. I used this instead and can confirm it works okay:

https://stackabuse.com/courses/graphs-in-python-theory-and-implementation/lessons/dijkstras-algorithm/ [[User:WhyYouAskMe|WhyYouAskMe]] ([[User talk:WhyYouAskMe|talk]]) 11:25, 4 September 2022 (UTC)

It will be interesting to see if this gets out of pre-print status into [[WP:RS]].

== Distracting animation ==

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

This article contains an infinitely looping animation which is placed right next to the text, and cannot be stopped. This is extremely distracting while reading, and can be a significant problem for some readers. I strongly suggest changing this so that the animation would only run on demand. [[User:BarroColorado|BarroColorado]] ([[User talk:BarroColorado|talk]]) 11:33, 22 September 2022 (UTC)

== Limitations of Dijkstra's algorithm ==

This algorithm cannot be applied for negative edge weights [[Special:Contributions/2409:4056:DB1:4F9F:7A9C:1055:D238:88CB|2409:4056:DB1:4F9F:7A9C:1055:D238:88CB]] ([[User talk:2409:4056:DB1:4F9F:7A9C:1055:D238:88CB|talk]]) 05:01, 12 October 2022 (UTC)