COIN-OR::LEMON - Graph Library

Opened 14 years ago

Last modified 8 years ago

#385 new enhancement

QuadHeap instead of BinHeap in Dijkstra

Reported by: Peter Kovacs Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.5 release
Component: core Version: hg main
Keywords: Cc:
Revision id:


It is questionable whether Dijkstra should use QuadHeap instead of BinHeap by default.

In theory, a fourary heap is at least as efficient as a binary heap independently of the actual use case. I made some benchmark tests in which QuadHeap turned out to be typically faster than BinHeap, especially when many decrease() operations are performed. See the benchmark results here. However, binary heap is the "standard" choice.

Change History (3)

comment:1 Changed 12 years ago by Peter Kovacs

In fact, this question does not seem to be important. I don't mind if it is closed. #381 seems to be much more interesting.

comment:2 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.3 releaseLEMON 1.4 release

comment:3 Changed 8 years ago by Alpar Juttner

Milestone: LEMON 1.4 releaseLEMON 1.5 release
Note: See TracTickets for help on using tickets.