Talk:Dijkstra's algorithm/Archive 2

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)

Algorithm > Pt. 4 (marking a visited) > claim of 'final and minimal'

Context: Responding to @IntGrah's edit's request to clarify why I feel that point 4 should refer reader to an aspect of point 5.

(Note that this is quite a fine detail of style, so probably not of big interest to most, but my edits were reverted, which suggest it had some importance to IntGrah).

The point 4 and 5 have a bit of a circular dependency which I will show below. Having said that, overall, I still think it's good that they are two separate points, because each information they give provides a new useful insight, but I see just one last fixable problem.

Namely, the claim of "distance recorded on the current node is final and minimal" does not yet follow from what the reader has read so far, especially that so far the reader does not know yet that there is going to be a loop, and how the 'current node' will change. It is only true thanks to the 5th point having "select the one with the smallest known distance" (if the step 5 selected any other node, it would not be true). I feel the insight of "this is the last time we are seeing this node" is helpful though, so I wouldn't remove it, but it would be helpful to admit, that this claim has not yet been justified, and point at where it will be justified, like I tried to do with 'see next step'. Otherwise the reader like me would stop and think they didn't understand something earlier. My new idea is, since @IntGrah points out it's not clear what aspect of step 5 is highlighted, that maybe it should explicitly state something like "(see next steps where the choice of next 'current node' always picks smallest distance)". Zlamma (talk) 12:30, 29 May 2024 (UTC)

It's important to note that this section is supposed to be a description of the algorithm, not a full fledged proof, so points which are justified inline with the algorithm should be brief. I think that the explanations you've written are a little too long. I understand your concern that the claim "final and minimal" is only justified in the next step; perhaps the earlier steps should deal with written to match the pseudocode more closely?

Currently, Step 2 says "Set the current node to be the starting node", Step 3 deals with the current node – "For the current node...", and Step 5 deals with the selection of the next node – "select the one with the smallest known distance".

To better approximate the actual algorithm, would you suggest rewriting Step 3 to be on the lines of "Select the unvisited node with the smallest distance to be the current node", remove the sentence from Step 2, and make Step 5 simply say "Go back to Step 3"?

With this structure, you could justify the points you made in step 4 much more concisely, rather than long proof sketches which refer to the next step. IntGrah (talk) 12:46, 29 May 2024 (UTC)

Your suggestions sound sensible to me. (Indeed I was trying to limit myself in the number of points changed, concerned that this would spark contention from many contributors that I would not be able to address, but collaboratively a change like this could be viable.)

Perhaps I would still add something like I wrote in bold here: "Select the unvisited node with the smallest distance to be the current node (on the first entry to this step, this is the starting node of distance zero)", just to make it easy to think about how the algorithm first engages the state, yet reaffirm that this is a universal instruction that handles all cases. Will leave it up to you though. Zlamma (talk) 13:35, 29 May 2024 (UTC)

Yes, this is what I had in mind for Step 2. I've incorporated it into the article; feel free to copyedit or point out any other issues with it. IntGrah (talk) 14:10, 29 May 2024 (UTC)

Thank you. The copy looks good.

I noticed that you still left no explicit information about justifies the 'finality', which I feel still can be helpful, and I interpret your "With this structure, you could justify the points you made in step 4 much more concisely" as allowing me to add the justification onto the new structure, so I did so already, to cut the conversation short. If you feel strongly that the reader should deduce this themselves, feel free to undo. Zlamma (talk) 15:16, 29 May 2024 (UTC)

Your explanation looks fine to me. Thank you. IntGrah (talk) 15:27, 29 May 2024 (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)

@Zlamma, since you're here, do you have any thoughts about what to do with this 'Description' section? IntGrah (talk) 15:37, 29 May 2024 (UTC)

Your impression about it being redundant seem justified to me, but I am not very experienced about what should or shouldn't be in an article. For what it's worth, I myself have never read the description when I came to this article to refresh my understanding - going straight to the Algorithm was sufficient, which adds to the redundancy vote, though I am a programmer - perhaps the Algorithm section isn't understandable to all, so maybe waiting for another voice here would make sense.

Other than this, first thought I had when I saw how that section is written was that maybe that text should go to the 'Simple English' language version of the article (could even give a link to there, above the Plain English 'Algorithm', to make it discoverable). But I can see that version does have a similarly ill-styled text in its Algorithm section already 🙂Zlamma (talk) 00:39, 30 May 2024 (UTC)

From what I know, Binary search algorithm is the only featured article for an algorithm, and it follows MOS:CS. If binary search, undoubtedly much simpler than Dijkstra, doesn't need a real-life example, I don't think this article needs it either.

I quite like the idea of incorporating it into simple English; I think the SE article would benefit from the terminology used here: place, road, map. I've not written a simple English before but it is possible. IntGrah (talk) 01:27, 30 May 2024 (UTC)