Content deleted Content added
m →Running Time: fixed silly wiki-generated name |
|||
Line 52:
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|
: 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|
:::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|Kh naba]] ([[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|Kh naba]] ([[User talk:Kh naba|talk]]) 10:27, 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|
::::: 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|
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)
| |||