Talk:Dijkstra's algorithm

This is the talk page for discussing improvements to the Dijkstra's algorithm article. This is not a forum for general discussion of the subject of the article.

Add new text under old text. New to Wikipedia? Welcome! Learn to edit; get help. Start a new topic Assume good faith Be polite and avoid personal attacks Be welcoming to newcomers Seek dispute resolution if needed Article policies Neutral point of view No original research Verifiability

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Archives: 1, 2Auto-archiving period: 12 months

This  level-5 vital article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computer science Top‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science Top This article has been rated as Top-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}} Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale. Computing High‑importance This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing High This article has been rated as High-importance on the project's importance scale.

Archives

Archive 1 Archive 2

This page has archives. Topics inactive for 365 days are automatically archived by Lowercase sigmabot III if there are more than 4.

The content of Uniform-cost search was merged into Dijkstra's algorithm. The former page's history now serves to provide attribution for that content in the latter page, and it must not be deleted as long as the latter page exists. For the discussion at that location, see its talk page.

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

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

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

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

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