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. |
Article policies
|
| 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.
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
| |||||||||||||||||||||||||||||||||||||||||||||||
|
||
|
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. |
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," ?
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)