|
== 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]? —[[User:Enervation|Enervation]] ([[User talk: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? [[Special:Contributions/2001:569:57B2:4D00:71E1:A843:C41:841C|2001:569:57B2:4D00:71E1:A843:C41:841C]] ([[User talk:2001:569:57B2:4D00:71E1:A843:C41:841C|talk]]) 16:22, 25 May 2022 (UTC)
== Pseudocode improvement ==
| 