|
|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>
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-->
"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">— 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-->
== Another interpretation of Dijkstra's Algorithm ==
== Add A Fact: "Dijkstra's algorithm proven universally optimal" ==
Here is one way to find the shortest distance from s to every other vertex in the graph:
I found a fact that might belong in this article. See the quote below
Let v be in G, and define o[v] to be the number of outgoing edges of v. Put o[v] little men on each each vertex v. These men are going to run a relay race. You fire the gun, and all the men on s start running at unit speed, one along each outgoing edge. Whenever a man reaches a vertex, all the men at that vertex run along the outing edges at unit speed. Notice that we are traversing all possible paths in the graph, and that the first man to get to vertex v gets there in the shortest time possible. Thus we've solved the problem.
<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:
Dijkstra's algorithm just simulates this process in discrete time intervals. The nth vertex added to S in Dijkstra's algorithm is the nth vertex reached by a little man.
<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:
I think this interpretation is very helpful in understanding the correctness of the algorithm. Should it be included in the article?
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.
:Josh Brown Kramer [[User:129.93.181.31|129.93.181.31]] 21:11, 9 November 2006 (UTC)
[[User:DKEdwards|DKEdwards]] ([[User talk:DKEdwards|talk]]) 18:37, 17 November 2024 (UTC)
This does not work, or it's not clear from your description that it works. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/71.120.113.27|71.120.113.27]] ([[User talk:71.120.113.27|talk]]) 15:09, 5 November 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
: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==
:: It's not bad, but a little unclear and a little misleading in its current form. It probably should say something like ''Let v be a vertex in graph G, s be the starting point and e be the ending point'' to introduce your terms. It should also read: ''For all v in G'' to indicate that all vertices have the little men and not just one vertex and I think where you write ''the first man to get to vertex v gets there...'' you mean to say something like ''the first man to get to vertex e'' or ''the first man to reach the destination''. You could also help clarify the paragraph by stating that the little men '''can only''' run at unit speed, thus avoid repeating the unit speed statement.
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)
::Finally, your metaphor does not deal with the fact that "visited" vertices are not "revisited" by Dijkstra's algorithm. This difference wouldn't make much of a difference, as the little man on the fastest path will get there regardless of little men running across already visited links, but this distinction should be at least mentioned. Other than that, this metaphor does seem instructive and I think could help explain the article. If you want help coming up with some phrasing, feel free to leave a note on my talk page -- cheers! [[User:jheiv|jhe<sub><small>iv</small></sub>]] ([[User_talk:jheiv |talk]]) 21:46, 6 January 2010 (UTC)
== Formatting of pseudocodes broken ==
== Error? ==
Look at node 4. 22 < 11 + 9 is an error.
If you were to change the 9 on the top of the graph to some large value like 36 for example, the algorithm as stated wouldn't seem to find the shortest path. Also, if the graph were mirrored (3 nodes connected to the start become 6) and mirrored indefinitely, and then the 3 mirror initial path choices reduced in value by say, 5, it isn't clear that the algorithm would halt, or it would pick the right direction. Another variant of this is if I were to drop a branch down from the initial start node with a distance value 2, and then connect it back to node 2 with a branch distance value some really high value, say 81, it isn't clear the algorithm would pick the correct branch to travel on, even if it correctly calculates the shortest distance. I know I'm misunderstanding the essential algorithm somehow, but the stated steps seem to leave too much in question and differ substantially from Dijkstra's own set descriptions. (another problems seems to arise if you divide up all the branches in two by placing another node in between any two nodes. The algorithm could be tricked by having a low initial distance value and then a higher distance value on the second half, this is a variant of the first error). Whose version of this algorithm is this? Which of my objections has any merit? I hope none, because I really like this algorithm, but I can't seem to wrap my mind around these ideas. How does the algorithm handle dead ends and direction? [[Special:Contributions/76.181.77.83|76.181.77.83]] ([[User talk:76.181.77.83|talk]]) 00:47, 17 January 2010 (UTC) Dan
:In your first example, it would work correctly. Notice that the last comparison is 20 (4) >= 20 (5). That means the algorithm is trying to reach the target vertex even after it has a finite value.
:In all the other examples you're saying that it isn't clear what the algorithm would do, but from the instructions, it's clear what would it do in each step, so the final result is clear too. (The only exception is when you have two or more unvisited vertices with the same lowest distance. In that case, the algorithm works correctly, no matter which one you choose.)
:I'm really not sure what do you think is the problem. Maybe you could describe one of the examples you gave in more detail, what do you think would happen and what exactly is wrong, not just “I think it doesn't work”.
:[[User:Svick|Svick]] ([[User talk:Svick|talk]]) 01:35, 17 January 2010 (UTC)
The change from @[[User:Lfstevens|Lfstevens]] on 8 December 2024, at 10:36 PM broke the formatting of the pseudocodes.<br>
:: It also might be helpful if you clarify what part of the article you have trouble with as there are a few that describe the algorithm (the sections "Algorithm", "Description of the algorithm", "Pseudocode", ...). [[User:jheiv|jhe<sub><small>iv</small></sub>]] ([[User_talk:jheiv |talk]]) 04:28, 17 January 2010 (UTC)
This also causes the pseudocode to be wrong since the nested loop is not recognizable (as nested) anymore.
:: I actually did describe several examples in detail, and I never said "I think it doesn't work" Not sure who you're quoting. In any case, I think it's best to deal with each of my objections piecemeal, so let's resolve each one in turn. Your first example high lights an inconsistency between the section "algorithm" and the graphic. The algorithm never has a step for comparing the source with the destination distance. If anything, read literally, the algorithm's last comparison before it halts would be to say 20<20+6, then it would not change 4's labeled distance and it would halt. At least at this fundamental level, how the graph and the section algorithm are written are inconsistent. Barring all of my other objections, this should raise a concern if the top 9 were changed to some horrendously large value like 50, the algorithm would successfully compare the distance through 3 to 6 and through 3 to 4, but would not compare the distance through 4 to 5 with distance through 6 to 5. When node 6 is current, we have what I have defined as a "dead end" comparison, where the algorithm is forced to conclude the minimal distance from target to source is 11+large number, say 11+50=61. So reading from the pseudocode section, the sequence S would incorrectly read {1,2,3,6,5} rather than the correct sequence {1,2,3,4,5,6}. I want to keep going, especially about how this gets to another ambiguity in the page, which is the difference between the pseudocode and the graphic and the description (why does it terminate at 5 being the last current node instead of 4? the algorithm finds the shortest distance path, independent of which node you choose as destination), but I feel these are probably quibbling details and the remainder of what I have discussed is interrelated with the first essential example. Thanks. [[Special:Contributions/76.181.66.9|76.181.66.9]] ([[User talk:76.181.66.9|talk]]) 15:31, 17 January 2010 (UTC) Dan
Last good version:<br>
:::<small>I quoted you, but not exactly, you said things like “wouldn't seem to find the shortest path”. That's the same as saying that it doesn't work, but not explaining in detail why you think so.</small>
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)
:::If the distance from vertex 6 to vertex 5 was 50, then, after visiting vertex 6, vertex 5 would really have a distance 61. But in the next step, unvisited vertex with the smallest distance would be 4, and the algorithm would change the distance of 5 to the correct value of 26 and <math>S</math> would be <math>\{1,2,3,4,5\}</math>.
:::I think I misunderstood what the animation meant by 20 (4) >= 20 (5). I thought it meant that the algorithm is trying to reach vertex 5 from 4, but in that case, there should be an arrow in the image and the vertex 4 should be marked as visited afterwards. What's really going on is that the algorithm chooses vertex 5 as the current node, because it has the smallest distance (along with vertex 4), and halts, because it's the target vertex.
:::[[User:Svick|Svick]] ([[User talk:Svick|talk]]) 10:57, 18 January 2010 (UTC)
:::: After some more careful thought on my part, the source of my confusion I think stems from the ambiguous wording of step 3 in the algorithm section. "For current node, consider all its unvisited neighbours and calculate their distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), OVERWRITE THE DISTANCE" (emphasis added) But which distance is being overwritten? I initially interpreted it as node B, or the non-current node connected to the current node because . This seems incorrect based on your last comment, and the version you understand makes much more sense than my interpretation. Another ambiguity is in regards to the first sentence: "calculate their distance (from the initial node)" which could mean sum all edge values connecting unvisited nodes to the current node with the current node's previously recorded distance. My proposed correction to step 3 is to have it worded thus: "For current node, consider each of its unvisited neighbors and calculate the distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this value is less than the previously recorded distance of either the current node or the unvisited neighbor, overwrite that node's distance with this value." This certainly seems to handle the problematic case we had been discussing. However, I was reading your comment and seem to have stumbled upon yet another error in the article, this time with the pseudocode (or perhaps your interpretation of it). The actual correct sequence, <math>S</math> would be <math>{1,3,6,5}</math> as the shortest path from a to b in the diagram. Essentially, the order the nodes are visited in is not necessarily isometric to a subsequence of shortest path between two nodes! Djikstra's algorithm does what it is supposed to do, calculate minimum distances, but another program needs to interpret how to arrive at these distances. What makes the algorithm so powerful is step 5 (obviously in conjunction with the others) which causes the algorithm to examine the paths that seem shortest first and avoids endless permutations. Thanks. [[Special:Contributions/76.181.77.83|76.181.77.83]] ([[User talk:76.181.77.83|talk]]) 16:57, 18 January 2010 (UTC) Dan
:::::No, you overwrite the distance of the neighboring node (B in the example), never of the current node. The <math>S</math> I talked about was for your changed graph. In the original, it really is <math>\{1,3,6,5\}</math> and can be found directly using this algorithm. [[User:Svick|Svick]] ([[User talk:Svick|talk]]) 17:42, 18 January 2010 (UTC)
::::::Explain how this does not directly contradict "If the distance from vertex 6 to vertex 5 was 50, then, after visiting vertex 6, vertex 5 would really have a distance 61. But in the next step, unvisited vertex with the smallest distance would be 4, and the algorithm would change the distance of 5." The only way you can do this "after visiting vertex 6" is to change 5's distance when 5 is the current node. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/76.181.77.83|76.181.77.83]] ([[User talk:76.181.77.83|talk]]) 18:11, 18 January 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
:::::::I'll write it in detail: (“o” means that the node was already visited – is out)
:::::::{| class=wikitable
! current !! 1 !! 2 !! 3 !! 4 !! 5 !! 6
|-
| colspan=7 style="text-align:center" | …
|-
| 3 || 0o || 7o || 9o || 20 || ∞ || 11
|-
| 6 || 0o || 7o || 9o || 20 || 50 || 11o
|-
| 4 || 0o || 7o || 9o || 20o || 26 || 11o
|-
| 5 || 0o || 7o || 9o || 20o || 26o || 11o
|}
:::::::As you can see, the change of the distance of 5 occurs, when 4 is the current node. [[User:Svick|Svick]] ([[User talk:Svick|talk]]) 17:55, 21 January 2010 (UTC)
::::::::thanks, I misread the last step in the algorithm section. It is very clear now. [[Special:Contributions/76.181.66.9|76.181.66.9]] ([[User talk:76.181.66.9|talk]]) 01:03, 22 January 2010 (UTC)Dan
== An interesting paper questioning optimality ==
== Greedy? ==
This paper "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths":
https://arxiv.org/abs/2504.17033
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-->
== What does '''fi ''' ; stand for ==
claims better-than-Dijkstra asymptotic performance in some edge cases.
in the code:
12 <big>''''''fi''''''</big> ;
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."
What does this '''''''fi''''''' stands for?
Ali Jamal--Ali Jamal 17:48, 8 December 2010 (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.
: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)
It will be interesting to see if this gets out of pre-print status into [[WP:RS]].
::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)
— [[User:The Anome|The Anome]] ([[User talk:The Anome|talk]]) 12:43, 1 June 2025 (UTC)
== Wrong anim? ==
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-->
| 