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.

Put new text under old text. Click here to start a new topic. New to Wikipedia? Welcome! Learn to edit; get help. 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 article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details. Computer science C‑class 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. C This article has been rated as C-class on Wikipedia's content assessment scale. 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}} Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details. Mathematics C‑class 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. C This article has been rated as C-class on Wikipedia's content assessment scale. Mid This article has been rated as Mid-priority on the project's priority scale. Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details. Computing C‑class 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. C This article has been rated as C-class on Wikipedia's content assessment scale. High This article has been rated as High-importance on the project's importance scale. Template:Vital article

Archives

Archive 1 Archive 2

This page has archives. Sections older than 365 days may be auto-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.

Terminological Dissonance?

The terminology in the caption for the animation is not in full agreement with the description of the algorithm: (a) the algorithm description does not mention a "tentative set" - it does mention "tentative distances", and it mentions an "unvisited set"; (b) the algorithm description mentions no "heuristic", but the caption to the animation says that the algorithm uses a "heuristic that is identically zero". At first it seemed to me that the caption of the animation intended "tentative set" to mean that which is meant by "unvisited set" in the algorithm description, but as I thought about it, I am unsure; on the other hand, it seems clear to me that even if that is not the intent of the caption, it does follow that the "tentative set" is identical to the "unvisited set" in that example. Matt Insall 13:15, 5 August 2017 (UTC) — Preceding unsigned comment added by Espresso-hound (talk • contribs)

Complexity with Fibonacci heaps

Latest comment: 7 years ago1 comment1 person in discussion

A few users have been changing the complexity with Fibonacci heaps from ${\displaystyle O(|E|+|V|\log |V|)}$  to ${\displaystyle O((|E|+|V|)\log |V|)}$  without any justification. The former appears to be correct based on the reasoning in the article:

For any implementation of the vertex set Q, the running time is in

${\displaystyle O(|E|\cdot T_{\mathrm {dk} }+|V|\cdot T_{\mathrm {em} })}$ ,

where ${\displaystyle T_{\mathrm {dk} }}$  and ${\displaystyle T_{\mathrm {em} }}$  are the complexities of the decrease-key and extract-minimum operations in Q, respectively.

since ${\displaystyle T_{\mathrm {dk} }=\Theta (1)}$  for Fibonacci heaps. Hence I am reverting the complexity with Fibonacci heaps back to ${\displaystyle O(|E|+|V|\log |V|)}$ . -- Paddu (talk) 15:44, 27 December 2017 (UTC)Reply

Is the algorithm description incorrect?

Latest comment: 7 years ago2 comments2 people in discussion

Step six of the algorithm section is:

"6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3."

I don't believe that's correct. Shouldn't the "tentative" be removed? Since this is an important article I wanted to be sure I was correct before editing it, but if it is incorrect we've already hit citogenesis.

Botlord (talk) 06:04, 21 February 2018 (UTC)Reply

It is the smallest among all the "tentative distances". While it is true that for the node with the smallest one, it is also the real distance, it is probably not so for the others, and even for that one it requires a proof, which will only be given after the algorithm has been described. --Alexey Muranov (talk) 06:25, 21 February 2018 (UTC)Reply

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

Animation incorrect/misleading?

Latest comment: 6 years ago1 comment1 person in discussion

The main animation is very confusing. It purports to minimize distance, but in the triangle formed by nodes 1-3-6, the distance between nodes 1 and 6 is labelled as 14, while the distance from node 1 to 3 to 6 sums to 11, which is geometrically imnpossible by the nature of triangles. Visually, the path 1-6-5 is obviously the shortest distance. Either the labels of the distances between nodes should be changed (and therefore the optimal path changed) or the description should be changed to not refer to distance and make clear that the labels do not reference distance between nodes. Am I seeing this correctly? Voyaging^talk 14:44, 11 July 2019 (UTC)Reply

Practical optimizations and infinite graphs

Latest comment: 5 years ago1 comment1 person in discussion

The pseudocode is a sort of Breadth-First Search, not Uniform-Cost Search, as it does not consider edge weight.129.241.229.8 (talk) 10:48, 9 January 2020 (UTC)Reply