Talk:Dijkstra's algorithm

The explanation makes no sense

Under Algorithm 2:
"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]"
You just assigned INFINITE to ALL. How is the shortest going to be find?

Under 3:
"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)"
Again, you assigned infinite to all nodes ...

I stopped reading it here. — Preceding unsigned comment added by 115.70.29.185 (talk) 08:49, 22 October 2024 (UTC)

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

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

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

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:

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

Perhaps it should also be noted in: https://en.wikipedia.org/wiki/Shortest_path_problem

This post was generated using the Add A Fact browser extension.

DKEdwards (talk) 18:37, 17 November 2024 (UTC)

What it actually means is that if

1. what you really want is the sorted order of vertices by distance from the source and not just the distances and paths,
2. you know ahead of time what graph you're going to run it on but not the weights, and
3. 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. —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. —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. Lfstevens (talk) 21:43, 9 December 2024 (UTC)

Quanta is often mush. —David Eppstein (talk) 21:49, 9 December 2024 (UTC)

Pseudocode

The pseudocode seems to fail into an endless loop unless all vertices are connected. 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. —David Eppstein (talk) 17:28, 24 November 2024 (UTC)

Formatting of pseudocodes broken

The change from @Lfstevens on 8 December 2024, at 10:36 PM broke the formatting of the pseudocodes.
This also causes the pseudocode to be wrong since the nested loop is not recognizable (as nested) anymore.

Last good version:
https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&oldid=1261954063 82.218.89.72 (talk) 07:06, 16 December 2024 (UTC)

An interesting paper questioning optimality

This paper:

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 $O(m\log ^{2/3}n)$-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 $O(m+n\log n)$ time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP."

— The Anome (talk) 12:43, 1 June 2025 (UTC)