COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 2 of Ticket #381


Ignore:
Timestamp:
07/31/10 23:48:02 (8 years ago)
Author:
Peter Kovacs
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #381 – Description

    initial v2  
    44A Dijkstra or Prim algorithm could be implemented with such heaps, but it would require slight modifications. A node should be pushed each time its distance label is updated (i.e. more than once in some cases), and the duplicate nodes should be skipped after each `pop()` operation.
    55
    6 This idea comes from the fact that the LEDA library also contains such an implementation of the binary heap structure and the Dijkstra algorithm, which turned out to be particularly efficient on some graphs. It was faster than the usual implementation by a factor between 1.5 and 2 on large graphs generated with NETGEN.
    7 
    8 Therefore, it would be nice to introduce such implementations in LEMON. I think, they would lead to better performance in many practical cases, because not too many duplications would be expected on typical graphs. However, there are some problems with this proposal. First, such heaps would not conform to the current heap concept. Second, using them would reqiure different implementation of the algorithms.
     6It would be nice to introduce such implementations in LEMON. I think, they would lead to better performance in many practical cases, because not too many duplications would be expected on typical graphs. However, there are some problems with this proposal. First, such heaps would not conform to the current heap concept. Second, using them would reqiure different implementation of the algorithms.