Talk:Dijkstra's algorithm/Archive 2

This is an archive of past discussions about Dijkstra's algorithm. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Archive 2

Wrong pseudo-code

The pseudo code mentions this:

24                  decrease-key v in Q;                           // Reorder v in the Queue

Then it mentions the same thing in the separate discussion of priority queue implementation:

19                 PQ.decrease_priority(v,alt)

Obviously, the first mention is wrong and the pseudo-code is, instead of talking about a normal queue, talking about the the same thing as priority queue section. I can make the change but I think more knowledgeable person ought to do it.--115.113.118.50 (talk) 07:12, 18 March 2014 (UTC)

Relaxation condition?

The article starts talking about the "relaxation condition" without defining it; I don't think this is very clear but I don't feel confident about editing it. http://stackoverflow.com/questions/2592769/what-is-the-relaxation-condition-in-graph-theory sort of explains (external link) but I can't find a decent definition within Wikipedia. — Preceding unsigned comment added by 88.104.125.53 (talk) 10:30, 12 April 2014 (UTC)

Cleaning up inconsistencies

I've tried to (begin to) address a few issues with this page that have been previously mentioned. Namely:

The first algorithm referred to a set, but then used priority queue operations on the set. A separate priority queue algorithm was then introduced. Either there should only be a single algorithm, or the first, simpler algorithm should stick to using a set
The algorithms referred to 'relaxing' edges without defining what this is or linking to a definition
The algorithms were inconsistent with each other, i.e. they did the same initialization in different ways. There were odd semicolons after some lines in the first algorithm, not the second.

I think there are larger issues with individual pages that use graphs being inconsistent with each other, and with the main Graph article itself. It would be nice if we could come up with a standard way of describing graphs and graphing algorithms, but these are bigger issues that will take a lot more work to address. --Peasaep (talk) 06:44, 25 May 2014 (UTC)

Proposed merge with Uniform-cost search

A look at Dijkstra's 1959 paper reveals that what he was describing is actually closer to what Russell and Norvig call UCS than the algorithm described in this page. The term UCS pops up in literature sometimes, but is equated with Dijkstra's algorithm by, e.g., Korf and Zhang, Klein and Manning. See Talk:A* search algorithm#Relation to uniform-cost search for a longer discussion about when an algorithm deserves to be called Dijkstra's.

Ping Kri, David Eppstein. QVVERTYVS (hm?) 10:36, 7 November 2014 (UTC)

Support: If Dijkstra's algorithm is so broad that it includes UCS (which it seems like it does in some cases) it feels unnecessary to have two articles for them.

It's funny—in the paper Divide-and-Conquer Frontier Search Applied to Optimal Sequence Alignment which you linked to they refer to Dijkstra's algorithm as a best-first search. I thought a best-first search was a kind of informed search, i.e. a search that is equipped with a heuristic, but looking in Russell and Norvig, it seems that this is not necessarily true either (although it is in most cases). It seems that it is very easy to have preconceptions when it comes to terminology of different algorithms. —Kri (talk) 13:54, 7 November 2014 (UTC)

Indeed, and in the context of branch and bound, "best-first" also means guided by a cost estimate heuristic (see, e.g., Clausen). I've never seen Dijkstra's being called that before. QVVERTYVS (hm?) 14:24, 7 November 2014 (UTC)

Yes UCS is uninformed. And a best-first search does not mean it has to be informed / have a heuristic. The main difference between UCS and Dijkstra is that UCS is tree search and Dijkstra is graph search. e.g.: Therefore UCS doesn't need to check for cycles. The target for the algorithms is different. Besides that, they are the same. (Source: Me studying for AI Exam) — Preceding unsigned comment added by 84.150.115.11 (talk) 23:57, 6 February 2015 (UTC)

@84.150.115.11: Russell and Norvig don't present UCS as a tree-only search algorithm. They present it as one strategy for filling in their Tree-Search and Graph-Search skeletons. QVVERTYVS (hm?) 13:53, 7 February 2015 (UTC)

There is a difference between dijistra's algorithm and UCS. see: http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/view/4017/4357 Goolig (talk) 14:27, 12 February 2015 (UTC)

"The main difference is the identity of the nodes in the priority queue. In DA, all nodes are initially inserted into the queue. In UCS, nodes are inserted to the queue lazily during the search." Interestingly, this is not the case in the Mehlhorn and Sanders textbook (ref in article). There, the nodes are pushed onto the queue upon first visit. The paper also states that "Based on Dijkstra’s own words [I] conjecture that he formulated his algorithm as UCS ... The name Dijkstra’s algorithm can/should still be used as he was perhaps the first to write about this logical behavior." So this an argument in favor of merging. QVVERTYVS (hm?) 15:21, 12 February 2015 (UTC)

I performed the merge. AIMA and the Felner paper found by Goolig is used to explain the similarities and differences between UCS/Dijkstra. QVVERTYVS (hm?) 20:27, 22 February 2015 (UTC)

Any video of animation available?

That animation is killing me. I so much want to carefully look at it's calculations, but they flash up there for just a half second. It is maddening.

That animation does not work as described. The calculated cost as shown in the animation is 20, while the correct one based on the described procedure is 28 (or 26 if bidirectional [1]) [1]: http://rosettacode.org/wiki/Dijkstra's_algorithm#Java — Preceding unsigned comment added by Ckorakidis (talk • contribs) 19:31, 17 October 2015 (UTC)

Description section of artice

In the second paragraph after the note, it says "This is done by determining the sum of the distance between an unvisited intersection and the value of the current intersection". There should be two intersections following between, but there is only one intersection since value is not an intersection.

The phrase, "This is done by determining the sum of the distance between an unvisited intersection and the value of the current intersection" should be changed to read, "This is done by adding the value of the current intersection to the distance between the current intersection and an unvisited intersection". RHB100 (talk) 00:34, 12 January 2016 (UTC)

Pronunciation of the inventor's name

Could we add the correct phonetical expression for the inventors name? Anyone researching for this topic will have trouble to pronounce the name correctly. — Preceding unsigned comment added by 2A02:8109:80C0:7EC:E8F6:F2B8:8896:A526 (talk) 10:33, 22 April 2016 (UTC)

Description: "Pencil arrows" vs. "parents"

A paragraph in the Description advises "in pencil, mark the road with an arrow pointing to the relabeled intersection." The next paragraph talks about a visited node's "parent." I think these are talking about the same thing, but it's not very clear. Perhaps better wording might be "by following the nodes' parents (that is, traversing the arrows backward)", or perhaps in the first paragraph, "mark the road with an arrow pointing to the relabeled intersection (from 'parent' to 'child')" --Jackrepenning (talk) 18:54, 24 September 2016 (UTC)

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

A few users have been changing the complexity with Fibonacci heaps from $O(|E|+|V|\log |V|)$ to $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

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

,

where

T_{\mathrm {dk} }

and

T_{\mathrm {em} }

are the complexities of the decrease-key and extract-minimum operations in

Q

, respectively.

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

Is the algorithm description incorrect?

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)

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)

Animation incorrect/misleading?

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)

Practical optimizations and infinite graphs

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

GIF is confusing

The gif of Dijkstra's implementation gives irrelevant information which is misleading and confusing - the values inside the nodes are pointless and contribute nothing to the understanding of the algorithm, while the excessive amount of information is confusing. A new gif with no values inside the nodes should be created. — Preceding unsigned comment added by 2A02:ED0:33B2:6C00:F5D1:308E:202D:179C (talk) 09:14, 10 September 2020 (UTC)

Dubious

In the section "Using a priority queue", we have:

Yet another alternative is to add nodes unconditionally to the priority queue and to instead check after extraction that no shorter connection was found yet. This can be done by additionally extracting the associated priority p from the queue and only processing further if p ≤ dist[u] inside the while Q is not empty loop.

https://cs.stackexchange.com/a/118406/ thinks that this is mistaken and should be replaced with p = dist[u]. Ryoji writes (CC-BY SA 4.0):

You are right. Checking k < d[u] is not sufficient and updating d[u] on the next line is not necessary.

The check prevents proceeding when the source is picked up from the queue (then k = 0 and d[s] = 0). Also, d[u] (u is fixed) is monotonically decreasing as loop proceeds, so even though it is updated after (u, d[u]) is put on the queue, k >= d[u] holds when (u,k) is picked up from the queue. Moreover, if d[u] is strictly smaller than k , the element should simply be ignored since it cannot be the shortest path to u.

You can change the condition to k == d[u] and remove following update to d[u].

Should we replace the condition with k == d[u]? —Enervation (talk) 16:44, 30 December 2020 (UTC)

Roads and intersections

Article says that "Note: For ease of understanding, this discussion uses the terms intersection, road and map – however, in formal terminology these terms are vertex, edge and graph, respectively."

This...doesn't make it easier. It actually sounds incredibly patronizing. Who in the right mind would try to learn Dijkstra's algorithm without knowing what a vertex is? 2001:569:57B2:4D00:71E1:A843:C41:841C (talk) 16:22, 25 May 2022 (UTC)

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)