Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 16:44, 30 December 2020

Revision as of 00:17, 31 December 2020

Line 16:

{{archives|auto=long|search=yes|bot=MiszaBot I|age=365}}

{{merged from|Uniform-cost search}}

== 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 [https://www.youtube.com/watch?v=gdmfOwyQlcI&t=20s we've already hit citogenesis].

[[User:Botlord|Botlord]] ([[User talk: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. --[[User:Alexey Muranov|Alexey Muranov]] ([[User talk: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? [[User:Voyaging|<span style="color:darkblue">'''''Voyaging'''''</span>]][[User talk:Voyaging|^{<span style="color:darkred">'''talk'''</span>}]] 14:44, 11 July 2019 (UTC)

== Practical optimizations and infinite graphs ==