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 article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

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

Archives: 1, 2: 12 months

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

	Mathematics portal 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. Sections older than 365 days may be automatically archived by when more than 4 sections are present.

The contents 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.

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

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

Description section issues

The section currently titled 'description' reads more like a tutorial on how to run Dijkstra by hand. It's full of 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. IntGrah (talk) 22:33, 26 April 2024 (UTC)[reply]

Consistency between Node and Vertex

The article uses 'node' in some places and 'vertex' in others. I propose changing them to 'vertex', since this is an algorithm on graphs, and 'vertex' is the more common term. This does not apply to sections where jargon has intentionally been removed. IntGrah (talk) 22:44, 26 April 2024 (UTC)[reply]

A priority queue implemented with a list is still a priority queue

To quote a sentence from the current revision:

Dijkstra's original algorithm does not use a min-priority queue and runs in time

\Theta (|V|^{2})

...

Dijkstra's 1959 paper did not specify how to find the node with minimal distance. This does not directly imply that Dijkstra implemented it with a list. Even if he did, this would still be a min-priority queue, because a priority queue is only an abstract data structure. But since he did not specify how to find the minimum, wouldn't it be best to not mention the words 'priority queue' at all? IntGrah (talk) 23:15, 26 April 2024 (UTC)[reply]