|
|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">— 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... <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/70.42.29.3|70.42.29.3]] ([[User talk:70.42.29.3|talk]]) 20:53, 4 May 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
I found a fact that might belong in this article. See the quote below
== Wrong anim? ==
<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:
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-->
<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:
Read the algorithm, it keeps the minimum distance. [[Special:Contributions/129.67.95.240|129.67.95.240]] ([[User talk:129.67.95.240|talk]]) 13:03, 9 August 2011 (UTC)
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.
== Python code ==
[[User:DKEdwards|DKEdwards]] ([[User talk:DKEdwards|talk]]) 18:37, 17 November 2024 (UTC)
According to [[WP:NOTREPOSITORY]], the python code should not be here. I suggest that it be deleted soon.
:What it actually means is that if
Please discuss it below.
:#what you really want is the sorted order of vertices by distance from the source and not just the distances and paths,
- [[User:Subh83| '''Subh83''']] <small>([[User_talk:Subh83|talk]] | [[User:Subh83/contribs|contribs]])</small> 17:29, 18 April 2011 (UTC)
:#you know ahead of time what graph you're going to run it on but not the weights, and
: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)
:#you can only access the weights by pairwise comparisons,
::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]] | [[User:Subh83/contribs|contribs]])</small> 22:25, 18 April 2011 (UTC)
: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)
== Running Time Pseudocode==
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)
The running time is mentioned as O((|E| + |V|)log |V|) if binary heap is used. I think it assumes Relax(v) = log|V|, but with real binary heap, the operation is "remove v from heap" and "re-add v" are O(|V|) and O(logV), resp., making Relax(v) = O(|V|). Hence, the total running time should be O(|V|log|V| + |E||V|). Can someone verify?
-- [[User:Kh naba|Naba Kumar]] ([[User talk:Kh naba|talk]]) 21:21, 26 May 2011 (UTC)
== Formatting of pseudocodes broken ==
: Removing an element from binary heap takes logarithmic time, so the bound in the article is correct. -- [[User:X7q|X7q]] ([[User talk:X7q|talk]]) 21:57, 26 May 2011 (UTC)
The change from @[[User:Lfstevens|Lfstevens]] on 8 December 2024, at 10:36 PM broke the formatting of the pseudocodes.<br>
:: Removing an element (in this case, a vertex) requires finding it first, which is O(|V|), not O(log|V|) - note: you don't know the index. Relax(v) can alternatively be defined as = find key (O(|V|)) + decrease-key (O(log |V|)) = O(|V|) -- [[User:Kh naba|Naba Kumar]] ([[User talk:Kh naba|talk]]) 22:13, 26 May 2011 (UTC)
This also causes the pseudocode to be wrong since the nested loop is not recognizable (as nested) anymore.
:::If you don't know the index and have to search sequentially for it, you're doing it wrong. In this case, you do know the index: it's always at the front of the heap. And more generally if you want to find the position of a vertex in a heap (say for decrease key operations) you can simply maintain an index for each vertex that stores its position in the heap, and change these indexes whenever you change the heap. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 22:52, 26 May 2011 (UTC)
Last good version:<br>
:::: The decrease-key operation I pointed out is not about removing from top, but a step that happens in between step 16 and 19 in pseudo code (it's implied, but rather should be written down for clarity). Also, it's not about being "wrong". Removing a non-min element from a binary heap can not be done below O(n) without datastructure augmentation as you just described, in which case the statement in the article "With a binary heap, the algorithm requires O((|E| + |V|)log |V|) time ..." is therefore wrong verbatim when applied to the pseudo code. At best, it's insufficient to describe a casual reader how one arrived at O((|E| + |V|)log |V|) as algorithm's performance. I think, the article should make this clarification and mention performance of both non-augmented and augmented structure. [[User:Kh naba|Naba Kumar]] ([[User talk:Kh naba|talk]]) 10:03, 28 May 2011 (UTC)
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 ==
:::: Okay, I have fixed the article by (1) adding step 19 explaining the need of decrease-key operation and (2) explaining runtime with and without the extra indexing. I believe this is much more clear now. Thanks for you inputs. [[User:Kh naba|Naba Kumar]] ([[User talk:Kh naba|talk]]) 10:27, 28 May 2011 (UTC)
This paper "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths":
https://arxiv.org/abs/2504.17033
::::: I don't think we need to list that suboptimal time. No one implements Dijkstra in that way. It's worse than Dijsktra without a heap (O(V^2) is better than O(VE + whatever) for connected graphs). A note explaining that an array of indexes into the binary heap is required to achieve stated time bounds would be useful though -- [[User:X7q|X7q]] ([[User talk:X7q|talk]]) 10:53, 28 May 2011 (UTC)
:::::: Agreed. I just rephrased it better. [[User:Kh naba|Naba Kumar]] ([[User talk:Kh naba|talk]]) 15:52, 28 May 2011 (UTC)
In addition, with a "vanilla binary heap" without the reverse index, it is still easy to get O(m log n) time: simply re-insert the vertex after each decrease-key ignoring the fact that it already has another entry in the heap, and check whenever you do a delete-min whether it's a vertex you've already seen. The disadcantage of doing it this way is primarily space (you get a heap entry per edge rather than per vertex). —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 15:41, 28 May 2011 (UTC)
claims better-than-Dijkstra asymptotic performance in some edge cases.
: I don't think that works in practice because the vertex being referenced by both the entries (the newly inserted and the old one) are indistinguishable since they are the same, and the "old one" is quite likely already in the wrong place in the heap because of the change in it's value. In addition, simply being just seen-before is probably not enough distinction because a vertex can possibly be decreased-key more than once (so a count is needed, rather than a flag). The reverse index approach is a sensible approach I see (albeit a bit dirty because you break abstraction of the Queue object by storing Queue data inside Vertex structure without having to resort to an external hashtable of vertex->heap_index). I hope someone identifies a cleaner data structure to use for the Queue instead of binary heap. [[User:Kh naba|Kh naba]] ([[User talk:Kh naba|talk]]) 16:12, 28 May 2011 (UTC)
::It does too work. I've implemented and tested it. You just have to ignore heap entries whose priority is larger than the already-determined distance for a vertex. And the reverse index is not only "a sensible approach", it is exactly the standard approach. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 16:21, 28 May 2011 (UTC)
:::Hmm, so you kept priorities to be separate from vertex min-distances, something like Q = [.., {v1, p1}, .. {v1, p2}, ..] and v1=[min_distance, previous ...]? That would certainly work. I had the queue totally depended on the vertex structures, like Q = [... v1, ... v1, ....] and v1 = [min_distance, previous, ...]. There, it doesn't work because min_distance is the priority in both instances of v1 - as seen by the queue. Your approach is clearly better (although it introduces additional structure {v,p} to hold the queue, but that's better than the reverse-index approach). Why not describe it in the article/pseudo-code so that others could follow it? -- [[User:Kh naba|Naba Kumar]] ([[User talk:Kh naba|talk]]) 19:24, 28 May 2011 (UTC)
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."
::: And thanks for pointing out this approach, I would go for this one instead of the reverse index one. --[[User:Kh naba|Naba Kumar]] ([[User talk:Kh naba|talk]]) 19:31, 28 May 2011 (UTC)
::::Re why not to add it to the article: because we need a reliable source that describes this alternative approach. I discussed it eight years ago [http://mail.python.org/pipermail/python-dev/2003-April/035013.html here] but I don't think that counts as a reliable source unless you want to go with the "established expert" clause of [[WP:SPS]] (plausible as I have published about other aspects of shortest paths but I'm certainly not going to add it myself). I don't know of published sources that talk about doing it this way. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 19:51, 28 May 2011 (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.
::::: Here's one source which talks about this idea: [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2#dijkstra3]. They further eliminate space disadvantage you mentioned by using a balanced tree (standard in C++) which does everything heaps can do plus an efficient find operation (if you know key's priority). -- [[User:X7q|X7q]] ([[User talk:X7q|talk]]) 20:54, 28 May 2011 (UTC)
:::::: @X7q: That's also an interesting approach. However, I see that "find" in the balanced-tree using the priority key could be risky because there can potentially be vertexes with same priority (you want to decrease-key your current vertex, not any vertex with same priority). I believe that's reason why this may not be a reliable choice. -- [[User:Kh naba|Naba Kumar]] ([[User talk:Kh naba|talk]]) 12:06, 31 May 2011 (UTC)
::::::: We use (priority, vertex number) pairs as keys in the tree, not just priorities. And there's at most one key per vertex - decrease-key operation is implemented by removing (previous priority, vertex) and inserting (new priority, vertex). This is why it works correctly. -- [[User:X7q|X7q]] ([[User talk:X7q|talk]]) 14:02, 31 May 2011 (UTC)
::::: @David: That approach is so useful for implementers, I would hazard "citation needed" and still mention it. Ideally, it could be described so that it's trivially logical, so as not to require external proof/citation. For example, as long as it is explained that priority of a vertex only reduces and never increases, and that the queue "does not care" about duplicate entries since old priorities are still intact for older entries for it to function correctly, then I think it can survive. It's a tip most people will easily miss (or re-invent) if not mentioned. Let me put this tip in article (with ref. to you, of course) and see if it survives scrutiny :). -- [[User:Kh naba|Naba Kumar]] ([[User talk:Kh naba|talk]]) 11:41, 31 May 2011 (UTC)
It will be interesting to see if this gets out of pre-print status into [[WP:RS]].
Is it certaint that Dijkstra in general has running time <math>O(|E| \cdot dk_Q + |V| \cdot em_Q)</math>? If sources are needed I highly recommend taking a look at this book: http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf (S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, 2006: "Algorithms"). High quality stuff written by world class researchers. Section 4.4 deals with Dijkstra specifically in the case with a priority queue with explicit definition of what is meant thereby. [[User:Superpronker|Superpronker]] ([[User talk:Superpronker|talk]]) 13:00, 7 June 2011 (UTC)
— [[User:The Anome|The Anome]] ([[User talk:The Anome|talk]]) 12:43, 1 June 2025 (UTC)
: In fact, in the abovementioned on page 125 (the box: "Which heap is best") it is stated that the running time is given as
::<math>|V| \cdot \mathtt{deletemin} + (|V| + |E|) \cdot \mathtt{decreasekey}</math>
: where the running time for decreasekey is the same as for insert key. This becomes important in explaining some of the running times. Please, someone, verify that I have got this correctly and update appropriately if there is a mistake in the article. [[User:Superpronker|Superpronker]] ([[User talk:Superpronker|talk]]) 14:03, 7 June 2011 (UTC)
== Algorithm ==
Step four of the algorithm is confusing. In its language it states that a visited nodes minimum distance will never be changed. This, is wrong as when the current node its switched a new minimum distance is calculated - keeping the distance that is minimum.
This is seen in the animation, where node 4 changes it value from 22 to 22 from steps 2 to 3.
Additionally, the end condition that 'all nodes' have been visited seems tenous, suppose an infinite undirected graph with two identified points (a,b), this would have infite computational time. The pseudocode on this page seems to address - can we make this less ambiguous? [[Special:Contributions/129.67.95.240|129.67.95.240]] ([[User talk:129.67.95.240|talk]]) 13:10, 9 August 2011 (UTC)
:It's not wrong: when node 4's distance changes that is the 'tentative distance' mentioned in step 3 changing. At that point node 4 is not the current node, node 3 is. 4 is being checked as a neighbor of the current node at 3.
:The all nodes termination is fine, too. Dijkstra's algorithm finds the minimal distance between a particular node and all other nodes in the graph (not a single destination), so it's obviously never going to terminate when run against an infinite graph. You need some variant of Dijkstra (such as [[A*_search_algorithm|A*]] to handle infinite graphs. - [[User:MrOllie|MrOllie]] ([[User talk:MrOllie|talk]]) 14:58, 9 August 2011 (UTC)
For me, the confusing steps are 2 and 3. On step 2, you mark all nodes as ''unvisited'' and next, on step 3, you add all neighbors of current node to the ''unvisited set''. Firstly, is there a reason for the unvisited-mark when having a visited-mark? Secondly, maybe the ''unvisited set'' is also unnecessary (as it just binds useful space), because the nodes belonging to this set are those who have distance less than infinity and are not marked as visited. [[User:Vevek|Vevek]] ([[User talk:Vevek|talk]]) 23:28, 15 August 2011 (UTC)
I would suggest to change line 3 in the code for getting the shortest path to:
1 ''S'' := empty sequence
2 ''u'' := ''target''
3 '''while''' ''u'' is defined:
4 insert ''u'' at the beginning of ''S''
5 ''u'' := previous[''u'']
6 '''end while''' ;
This way, you also get the start node. This is not the case in the current version. [[User:Milcke|Milcke]] ([[User talk:Milcke|talk]]) 17:06, 8 October 2011 (UTC)
| 