COIN-OR::LEMON - Graph Library

Opened 7 years ago

Last modified 15 months ago

#385 new enhancement

QuadHeap instead of BinHeap in Dijkstra

Reported by: kpeter Owned by: alpar
Priority: major Milestone: LEMON 1.5 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

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 6 years ago by kpeter

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 5 years ago by alpar

  • Milestone changed from LEMON 1.3 release to LEMON 1.4 release

comment:3 Changed 15 months ago by alpar

  • Milestone changed from LEMON 1.4 release to LEMON 1.5 release
Note: See TracTickets for help on using tickets.