Talk:Dijkstra's algorithm

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

Pseudocode improvement

In first pseudocode block, on line 15, dist[u] is checked for not being INFINITY. But if it is INFINITY at this point, the code will continue useless looping, because all remaining vertices will also have dist[u]=INFINITY and not influence the result. Maybe move the INFINITY check to line 11 and break out of while block, it would be more human readable too I think --Shrddr (talk) 20:44, 20 August 2022 (UTC)

We should stick to sources rather than commit WP:OR. CLRS has

DIJKSTRA(G, w, s)                 // Graph G, weights w, source vertex s
1 INITIALIZE-SINGLE-SOURCE(G, s)  // lines 3-5 of our algorithm
2 S = 0                           // empty set
3 Q = G.V                         // line 6
4 while Q non empty
5     u = EXTRACT-MIN(Q)          // line 10, 11
6     S = S union {u}
7     for each vertex  v in G:Adj(u)  // slightly different to ours
8        RELAX(u,v,w)

where RELAX is

RELAX(u, v, w)
1    if v.dist > u.dist + w(u, v)
2        v.dist = u.dist + w(u, v)
3        v.prev = u

There is nothing in this algorithm with a test of u.dist being infinity. So I think its safe to remove the condition entirely. --Salix alba (talk): 10:44, 21 August 2022 (UTC)

The text before pseudocode box ends with reference to https://doi.org/10.1007%2F978-3-540-77978-0 which does mention infinity check (see "algorithm" at page 197). But then for some reason it's left out in "pseudocode" at page 198. Shrddr (talk) 12:51, 21 August 2022 (UTC)

Pseudocode is wrong

The pseudocode that uses a priority queue is plain wrong, it produces garbage. I used this instead and can confirm it works okay: https://stackabuse.com/courses/graphs-in-python-theory-and-implementation/lessons/dijkstras-algorithm/ WhyYouAskMe (talk) 11:25, 4 September 2022 (UTC)

Distracting animation

This article contains an infinitely looping animation which is placed right next to the text, and cannot be stopped. This is extremely distracting while reading, and can be a significant problem for some readers. I strongly suggest changing this so that the animation would only run on demand. BarroColorado (talk) 11:33, 22 September 2022 (UTC)

Proof of correctness is incomprehensible

This section is full of grammar issues that make it very difficult to understand. Maybe it should be rewritten. Indicere (talk) 03:10, 28 January 2023 (UTC)

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)

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)

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)