|
[https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#/media/File:Dijkstra_Animation.gif That animation] does not work as described. The calculated cost as shown in the animation is 20, while the correct one based on the described procedure is 28 (or 26 if bidirectional [1])
[1]: http://rosettacode.org/wiki/Dijkstra's_algorithm#Java <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Ckorakidis|Ckorakidis]] ([[User talk:Ckorakidis|talk]] • [[Special:Contributions/Ckorakidis|contribs]]) 19:31, 17 October 2015 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
== Cleaning up inconsistencies ==
I've tried to (begin to) address a few issues with this page that have been previously mentioned. Namely:
* The first algorithm referred to a '''set''', but then used priority queue operations on the set. A separate priority queue algorithm was then introduced. Either there should only be a single algorithm, or the first, simpler algorithm should stick to using a set
* The algorithms referred to 'relaxing' edges without defining what this is or linking to a definition
* The algorithms were inconsistent with each other, i.e. they did the same initialization in different ways. There were odd semicolons after some lines in the first algorithm, not the second.
I think there are larger issues with individual pages that use graphs being inconsistent with each other, and with the main [[Graph]] article itself. It would be nice if we could come up with a standard way of describing graphs and graphing algorithms, but these are bigger issues that will take a lot more work to address. --[[User:Peasaep|Peasaep]] ([[User talk:Peasaep|talk]]) 06:44, 25 May 2014 (UTC)
== Proposed merge with [[Uniform-cost search]] ==
A look at Dijkstra's 1959 paper reveals that what he was describing is actually closer to what Russell and Norvig call UCS than the algorithm described in this page. The term UCS pops up in literature sometimes, but is equated with Dijkstra's algorithm by, e.g., [http://www.aaai.org/Papers/AAAI/2000/AAAI00-140.pdf Korf and Zhang], [http://machinelearning.wustl.edu/mlpapers/paper_files/CS01.pdf Klein and Manning]. See [[Talk:A* search algorithm#Relation to uniform-cost search]] for a longer discussion about when an algorithm deserves to be called Dijkstra's.
Ping {{U|Kri}}, {{U|David Eppstein}}. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small> 10:36, 7 November 2014 (UTC)
*'''Support:''' If ''Dijkstra's algorithm'' is so broad that it includes UCS (which it seems like it does in some cases) it feels unnecessary to have two articles for them.
:It's funny—in the paper ''Divide-and-Conquer Frontier Search Applied to Optimal Sequence Alignment'' which you linked to they refer to Dijkstra's algorithm as a [[best-first search]]. I thought a best-first search was a kind of informed search, i.e. a search that is equipped with a [[Heuristic (computer science)|heuristic]], but looking in Russell and Norvig, it seems that this is not necessarily true either (although it is in most cases). It seems that it is very easy to have preconceptions when it comes to terminology of different algorithms. —[[User:Kri|Kri]] ([[User talk:Kri|talk]]) 13:54, 7 November 2014 (UTC)
::Indeed, and in the context of [[branch and bound]], "best-first" also means guided by a cost estimate heuristic (see, e.g., [http://www.diku.dk/OLD/undervisning/2003e/datV-optimer/JensClausenNoter.pdf Clausen]). I've never seen Dijkstra's being called that before. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small> 14:24, 7 November 2014 (UTC)
* Yes UCS is uninformed. And a best-first search does not mean it has to be informed / have a heuristic. The main difference between UCS and Dijkstra is that UCS is tree search and Dijkstra is graph search. e.g.: Therefore UCS doesn't need to check for cycles. The target for the algorithms is different. Besides that, they are the same. (Source: Me studying for AI Exam) <small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/84.150.115.11|84.150.115.11]] ([[User talk:84.150.115.11|talk]]) 23:57, 6 February 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
::{{Re|84.150.115.11}} Russell and Norvig don't present UCS as a tree-only search algorithm. They present it as one strategy for filling in their Tree-Search and Graph-Search skeletons. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small> 13:53, 7 February 2015 (UTC)
* There is a difference between dijistra's algorithm and UCS. see: http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/view/4017/4357 [[User:Goolig|Goolig]] ([[User talk:Goolig|talk]]) 14:27, 12 February 2015 (UTC)
:* "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)
== Description section of artice ==
| 