| 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 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)
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?
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? Voyagingtalk 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)