Talk:Dijkstra's algorithm

Any video of animation available?

That animation is killing me. I so much want to carefully look at it's calculations, but they flash up there for just a half second. It is maddening.

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 — Preceding unsigned comment added by Ckorakidis (talk • contribs) 19:31, 17 October 2015 (UTC)

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. --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., Korf and Zhang, 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 Kri, David Eppstein. QVVERTYVS (hm?) 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, 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. —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., Clausen). I've never seen Dijkstra's being called that before. QVVERTYVS (hm?) 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) — Preceding unsigned comment added by 84.150.115.11 (talk) 23:57, 6 February 2015 (UTC)

@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. QVVERTYVS (hm?) 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 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. QVVERTYVS (hm?) 15:21, 12 February 2015 (UTC)

I performed the merge. AIMA and the Felner paper found by Goolig is used to explain the similarities and differences between UCS/Dijkstra. QVVERTYVS (hm?) 20:27, 22 February 2015 (UTC)

Description section of artice

In the second paragraph after the note, it says "This is done by determining the sum of the distance between an unvisited intersection and the value of the current intersection". There should be two intersections following between, but there is only one intersection since value is not an intersection.

The phrase, "This is done by determining the sum of the distance between an unvisited intersection and the value of the current intersection" should be changed to read, "This is done by adding the value of the current intersection to the distance between the current intersection and an unvisited intersection". RHB100 (talk) 00:34, 12 January 2016 (UTC)

Pronounciation of the inventors name

Could we add the correct phonetical expression for the inventors name? Anyone researching for this topic will have trouble to pronounce the name correctly.