Talk:Dijkstra's algorithm

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)

Read it again. In the first sentence: the starting node is set to zero; only the other nodes are set to infinite. That's how you start. During the later steps, infinite values are replaced with finite values when they are pathable from the start. Jon of All Trades (talk) 16:08, 6 September 2025 (UTC)

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)

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 ${\displaystyle 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 ${\displaystyle O(m+n\log n)}$ 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.

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

It would be nice if wikipedia authors could choose to use a consistent convention. Either use node, or use vertex. It's unsettling to a certain degree when, within a single article, no consistent symbology / terminology is employed. ~2026-80772-8 (talk) 17:48, 5 February 2026 (UTC)