Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 00:18, 16 June 2015

Latest revision as of 12:57, 1 June 2025

(90 intermediate revisions by 40 users not shown)

Line 3:

|archiveheader = {{talkarchivenav}}

|maxarchivesize = 70K

|counter = 12

|minthreadsleft = 4

|algo = old(365d)

|archive = Talk:Dijkstra's algorithm/Archive %(counter)d

}}

{{WikiProject banner shell|class=C|vital=yes|1=

{{WikiProjectBannerShell|1=

{{WikiProject Computer science|class=C |importance=top}}

{{mathsWikiProject rating|frequentlyviewed=yes|class=CMathematics|priority=Mid|field=discrete }}

{{WikiProject Computing|class=C |importance=High}}

}}

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

{{merged from|Uniform-cost search}}

== AnyThe videoexplanation ofmakes animationno available?sense ==

Under Algorithm 2: <br>

"Assign to every node a distance from start value: for the starting node, it is zero, and for all other nodes, it is infinity, since initially no path is known to these nodes. During execution of the algorithm, the distance of a node N is the length of the shortest path discovered so far between the starting node and N.[17]" <br>

You just assigned INFINITE to ALL. How is the shortest going to be find? <br><br>

Under 3:<br>

"From the unvisited set, select the current node to be the one with the smallest finite distance; initially, this will be the starting node, which has distance zero. If the unvisited set is empty, or contains only nodes with infinite distance (which are unreachable)"<br>

Again, you assigned infinite to all nodes ... <br><br>

I stopped reading it here. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/115.70.29.185|115.70.29.185]] ([[User talk:115.70.29.185#top|talk]]) 08:49, 22 October 2024 (UTC)</small> <!--Autosigned by SineBot-->

That animation is ki8lling 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.

== Add A Fact: "Dijkstra's algorithm proven universally optimal" ==

== Wrong pseudo-code ==

The pseudo code mentions this:

I found a fact that might belong in this article. See the quote below

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

<blockquote>

Dijkstra’s algorithm was long thought to be the most efficient way to find a graph’s best routes. Researchers have now proved that it’s “universally optimal.”

</blockquote>

The fact comes from the following source:

: https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/

Here is a wikitext snippet to use as a reference:

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

<nowiki> {{Cite web |title=Computer Scientists Establish the Best Way to Traverse a Graph |url=https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/ |website=Quanta Magazine |date=2024-10-25 |access-date=2024-11-17 |language=en |first=Ben |last=Brubaker |quote=Dijkstra’s algorithm was long thought to be the most efficient way to find a graph’s best routes. Researchers have now proved that it’s “universally optimal.”}} </nowiki>

Perhaps it should also be noted in:

19 PQ.decrease_priority(v,alt)

https://en.wikipedia.org/wiki/Shortest_path_problem

This post was generated using the [[:meta:Future_Audiences/Experiment:Add_a_Fact|Add A Fact]] browser extension.

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.--[[Special:Contributions/115.113.118.50|115.113.118.50]] ([[User talk:115.113.118.50|talk]]) 07:12, 18 March 2014 (UTC)

[[User:DKEdwards|DKEdwards]] ([[User talk:DKEdwards|talk]]) 18:37, 17 November 2024 (UTC)

== Relaxation condition? ==

:What it actually means is that if

:#what you really want is the sorted order of vertices by distance from the source and not just the distances and paths,

:#you know ahead of time what graph you're going to run it on but not the weights, and

:#you can only access the weights by pairwise comparisons,

:then a specific version of Dijkstra (with a special priority queue) will get a number of comparisons within a constant factor of optimal. It's a nice result, and probably should be mentioned in this article ([[Dijkstra's algorithm]]) but I question the relevance to [[shortest path problem]] because it's about sorting rather than shortest paths per se. It may have been a bit oversold by Quanta. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 21:14, 17 November 2024 (UTC)

::[[User:Lfstevens]]: when adding this material, it would have been helpful for you to have read this thread. Your version of what they did is far too vague and hypey. I have edited it to more accurately reflect the claims of the new paper. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 08:01, 9 December 2024 (UTC)

:::Thanks for noticing and fixing my mush. It was pretty much a pull from the Quanta piece. [[User:Lfstevens|Lfstevens]] ([[User talk:Lfstevens|talk]]) 21:43, 9 December 2024 (UTC)

::::''Quanta'' is often mush. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 21:49, 9 December 2024 (UTC)

==Pseudocode==

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. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/88.104.125.53|88.104.125.53]] ([[User talk:88.104.125.53|talk]]) 10:30, 12 April 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

The pseudocode seems to fail into an endless loop unless all vertices are connected. [[User:Kkddkkdd|Kkddkkdd]] ([[User talk:Kkddkkdd|talk]]) 17:32, 23 November 2024 (UTC)

:The pseudocode removes a vertex from Q in every iteration, starting with all vertices. It cannot get into an endless loop. If the graph is not connected then some vertices will have priority infinity when they are removed, but that is not a problem for the algorithm. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:28, 24 November 2024 (UTC)

== Cleaning up inconsistencies ==

== Formatting of pseudocodes broken ==

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.

The change from @[[User:Lfstevens|Lfstevens]] on 8 December 2024, at 10:36 PM broke the formatting of the pseudocodes.<br>

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)

This also causes the pseudocode to be wrong since the nested loop is not recognizable (as nested) anymore.

Last good version:<br>

== Proposed merge with [[Uniform-cost search]] ==

https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&oldid=1261954063 [[Special:Contributions/82.218.89.72|82.218.89.72]] ([[User talk:82.218.89.72|talk]]) 07:06, 16 December 2024 (UTC)

== An interesting paper questioning optimality ==

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.

This paper "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths":

https://arxiv.org/abs/2504.17033

Ping {{U|Kri}}, {{U|David Eppstein}}. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small> 10:36, 7 November 2014 (UTC)

claims better-than-Dijkstra asymptotic performance in some edge cases.

*'''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.

The abstract reads as follows: "We give a deterministic <math>O(m\log^{2/3}n)</math>-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the <math>O(m+n\log n)</math> time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP."

: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)

They cite the earlier work on proof of universal optimality, and state that Dijkstra's algorithm is still optimal ''if you want to know the order of the points in the path''; their algorithm does not produce this ordering.

::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)

It will be interesting to see if this gets out of pre-print status into [[WP:RS]].

* 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">—&nbsp;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-->

&mdash; [[User:The Anome|The Anome]] ([[User talk:The Anome|talk]]) 12:43, 1 June 2025 (UTC)

::{{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)