Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 20:53, 4 May 2011

Latest revision as of 12:57, 1 June 2025

(187 intermediate revisions by 76 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}}

== The explanation makes no sense ==

== Pretty muddy ==

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

if you try to take the psudocode and directly turn it into code. Well by 5 lines an it fails. set all distance to infinity. Then you check to see if edge distance is infinity? ofc it was, you just set it to that, and now you exit. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/64.134.224.50|64.134.224.50]] ([[User talk:64.134.224.50|talk]]) 00:50, 21 March 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

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

Reply:

Well actually you set the root to 0, so that will be smaller than infinity, then you set its neighbors and so on...

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

== Greedy? ==

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

Within the description it says 'this is the "greedy" part, as described above'. 'Greed' is not mentioned before the description, probably an editing error. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/93.96.163.250|93.96.163.250]] ([[User talk:93.96.163.250|talk]]) 17:31, 15 April 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

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

== What does '''fi ''' ; stand for ==

Perhaps it should also be noted in:

in the code:

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

12 <big>''''''fi''''''</big> ;

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

What does this '''''''fi''''''' stands for?

Ali Jamal--Ali Jamal 17:48, 8 December 2010 (UTC)

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

:It's an overly-cute but standard notation for the end of the block of code that begins with an "if". More specifically, it is "if" spelled backwards. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:54, 8 December 2010 (UTC)

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

::I move that it be changed to "end if," seeing as how that's what's used for "end for." -- [[User:GAMEchief|Charles Stover]] 20:16, 8 December 2010 (UTC)

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)

== Wrong anim? ==

== Formatting of pseudocodes broken ==

Look at the anim. First it goes to node #2. then when it wants to go to node #3 it count the length 9. it's absolutely wrong because if you want to go from #2 to #3 you must pass from a edge length 10. So what's the meaning of this? can anyone explain it for me? <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/109.162.218.57|109.162.218.57]] ([[User talk:109.162.218.57|talk]]) 12:31, 7 April 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

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

== Python code ==

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

Last good version:<br>

According to [[WP:NOTREPOSITORY]], the python code should not be here. I suggest that it be deleted soon.

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)

Please discuss it below.

- [[User:Subh83| '''Subh83''']] <small>([[User_talk:Subh83|talk]] &#124; [[User:Subh83/contribs|contribs]])</small> 17:29, 18 April 2011 (UTC)

== An interesting paper questioning optimality ==

:I don't agree that Python code is never justified on Wikipedia — often it can make a good alternative to pseudocode as a way of communicating the essence of an algorithm. But in this case I don't think it adds much to the pseudocode that is already here, especially since the style of writing gives up most of the advantages of conciseness and readability that Python usually has. So in this case I agree that it should be deleted. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:03, 18 April 2011 (UTC)

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

::Removed it. <br/>Although I agree Python codes are quite intuitive in general, I am not sure if any specific language should be preferred since may programmers may not use that language and may be unfamiliar with the specific syntaxes. Also, preferred syntaxes may vary between versions of the programing language ([[Wikipedia:Algorithms_on_Wikipedia]]). - [[User:Subh83| '''Subh83''']] <small>([[User_talk:Subh83|talk]] &#124; [[User:Subh83/contribs|contribs]])</small> 22:25, 18 April 2011 (UTC)

https://arxiv.org/abs/2504.17033

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

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."

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.

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

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