Content deleted Content added
→Running Time: vanilla binary heap |
|||
Line 63:
::::: 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)
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)
| |||