Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 09:15, 10 September 2020

Revision as of 16:44, 30 December 2020

Line 44:

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. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2A02:ED0:33B2:6C00:F5D1:308E:202D:179C|2A02:ED0:33B2:6C00:F5D1:308E:202D:179C]] ([[User talk:2A02:ED0:33B2:6C00:F5D1:308E:202D:179C#top|talk]]) 09:14, 10 September 2020 (UTC)</small> <!--Autosigned by SineBot-->

== 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)