Content deleted Content added
Line 65:
:::::: Agreed. I just rephrased it better. [[User:Kh naba|Kh naba]] ([[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)
| |||