Content deleted Content added
Line 67:
: 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)
| |||