Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 20:26, 22 February 2015

Revision as of 20:27, 22 February 2015

Line 59:

:* "The main difference is the identity of the nodes in the priority queue. In DA, all nodes are initially inserted into the queue. In UCS, nodes are inserted to the queue lazily during the search." Interestingly, this is not the case in the Mehlhorn and Sanders textbook (ref in article). There, the nodes are pushed onto the queue upon first visit. The paper also states that "Based on Dijkstra’s own words [I] conjecture that he formulated his algorithm as UCS ... The name Dijkstra’s algorithm can/should still be used as he was perhaps the first to write about this logical behavior." So this an argument in favor of merging. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small> 15:21, 12 February 2015 (UTC)

I performed the merge. ''AIMA'' and the Felner paper found by {{U|Goolig}} is used to explain the similarities and differences between UCS/Dijkstra. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small> 20:27, 22 February 2015 (UTC)