Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 12:47, 29 May 2024

Latest revision as of 12:57, 1 June 2025

(31 intermediate revisions by 11 users not shown)

Line 16:

{{merged from|Uniform-cost search}}

== The explanation makes no sense ==

== Description section issues ==

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 section currently titled 'description' reads more like a [[Wikipedia:NOTHOW|tutorial]] on how to run Dijkstra by hand. It's full of [[WP:YOU|second person]] and even tells you to use a pencil and follow along. Aside from that, it's just a complete restatement of the 'Algorithm' section, except in the context of city roads, jargon removed. It is of course necessary to provide an explanation that can be understood by the general reader, but this is redundant and not the way to do it. [[User:IntGrah|IntGrah]] ([[User talk:IntGrah|talk]]) 22:33, 26 April 2024 (UTC)

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

== Algorithm > Pt. 4 (marking a visited) > claim of 'final and minimal' ==

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

''Context: Responding to @[[User:IntGrah|IntGrah]]'s [https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&oldid=1226218209 edit]'s request to clarify why I feel that point 4 should refer reader to an aspect of point 5.''

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

(Note that this is quite a fine detail of style, so probably not of big interest to most, but my edits were reverted, which suggest it had some importance to [[User:IntGrah|IntGrah]]).

<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 point 4 and 5 have a bit of a circular dependency which I will show below. Having said that, overall, I still think it's good that they are two separate points, because each information they give provides a new useful insight, but I see just one last fixable problem.

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.

Namely, the claim of ''"distance recorded on the current node is final and minimal"'' does not yet follow from what the reader has read so far, especially that so far the reader does not know yet that there is going to be a loop, and how the 'current node' will change. It is only true thanks to the 5th point having ''"select the one with the smallest known distance"'' (if the step 5 selected any other node, it would not be true). I feel the insight of "this is the last time we are seeing this node" is helpful though, so I wouldn't remove it, but it would be helpful to admit, that this claim has not yet been justified, and point at where it will be justified, like I tried to do with 'see next step'. Otherwise the reader like me would stop and think they didn't understand something earlier. My new idea is, since @[[User:IntGrah|IntGrah]] points out it's not clear what aspect of step 5 is highlighted, that maybe it should explicitly state something like ''"(see next steps where the choice of next 'current node' always picks smallest distance)"''. [[User:Zlamma|Zlamma]] ([[User talk:Zlamma|talk]]) 12:30, 29 May 2024 (UTC)

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

:It's important to note that this section is supposed to be a description of the algorithm, not a full fledged proof, so points which are justified inline with the algorithm should be brief. I think that the explanations you've written are a little too long. I understand your concern that the claim "final and minimal" is only justified in the next step; perhaps the earlier steps should deal with "srewritten to match the pseudocode more closely?

:What it actually means is that if

:Currently, Step 2 says "Set the current node to be the starting node", Step 3 deals with the current node – "For the current node...", and Step 5 deals with the selection of the next node – "select the one with the smallest known distance".

:#what you really want is the sorted order of vertices by distance from the source and not just the distances and paths,

:To better approximate the actual algorithm, would you suggest rewriting Step 3 to be on the lines of "Select unvisited node with the smallest distance to be the current node"? Then, Step 2 will not need such a sentence, and Step 5 can simply say "Go back to Step 3".

:#you know ahead of time what graph you're going to run it on but not the weights, and

:With this structure, you could justify the points you made in step 4 much more concisely, rather than long proof sketches which refer to the next step. [[User:IntGrah|IntGrah]] ([[User talk:IntGrah|talk]]) 12:46, 29 May 2024 (UTC)

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

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)

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

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)