|
I think I spotted another error: when an arrow is drawn from node #3 to node #4, a question mark and subsequently " 22 < 11 + 9 " is written above node #4. Shouldn't the inequality sign be the other way? [[Special:Contributions/109.129.178.210|109.129.178.210]] ([[User talk:109.129.178.210|talk]]) 06:47, 28 April 2012 (UTC)
== Python code ==
According to [[WP:NOTREPOSITORY]], the python code should not be here. I suggest that it be deleted soon.
Please discuss it below.
- [[User:Subh83| '''Subh83''']] <small>([[User_talk:Subh83|talk]] | [[User:Subh83/contribs|contribs]])</small> 17:29, 18 April 2011 (UTC)
: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)
::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)
== Running Time ==
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)
: 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)
:: 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)
:::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)
:::: 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)
:::: 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)
::::: 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)
: 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)
::: 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)
::::: 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)
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)
: 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 ==
| 