Talk:Dijkstra's algorithm/Archive 2

Archive 1

Archive 2

Wrong pseudo-code

The pseudo code mentions this:

24                  decrease-key v in Q;                           // Reorder v in the Queue

Then it mentions the same thing in the separate discussion of priority queue implementation:

19                 PQ.decrease_priority(v,alt)

Obviously, the first mention is wrong and the pseudo-code is, instead of talking about a normal queue, talking about the the same thing as priority queue section. I can make the change but I think more knowledgeable person ought to do it.--115.113.118.50 (talk) 07:12, 18 March 2014 (UTC)

Relaxation condition?

The article starts talking about the "relaxation condition" without defining it; I don't think this is very clear but I don't feel confident about editing it. http://stackoverflow.com/questions/2592769/what-is-the-relaxation-condition-in-graph-theory sort of explains (external link) but I can't find a decent definition within Wikipedia. — Preceding unsigned comment added by 88.104.125.53 (talk) 10:30, 12 April 2014 (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)