Boost logo

Boost :

From: (noreply_at_[hidden])
Date: 2005-03-24 14:35:05

Bugs item #1170106, was opened at 2005-03-24 14:35
Message generated for change (Tracker Item Submitted) made by Item Submitter
You can respond by visiting:

Category: graph
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Douglas Gregor (dgregor)
Assigned to: Douglas Gregor (dgregor)
Summary: Investigate other kinds of heaps for dijkstra_shortest_paths

Initial Comment:
There are many types of heaps that provide good theoretical
performance when used as a priority queue, e.g., by Dijkstra's
shortest paths algorithm. The BGL contains implementations of two
such data structures: a binary heap and a relaxed heap. The latter is
used because it has been shown to provide the best overall
performance. However, we should investigate other kinds of heaps,
e.g., Fibonacci heaps, relaxed Fibonacci heaps, and run-relaxed
heaps, to determine which option is best for the BGL.

Dietmar Kuhl implemented several kinds of heaps in his Heaps
library, which could be found in earlier versions of Boost. It was
removed from Boost in the 1.27.0 timeframe because it had never
been reviewed and was not maintained, but may still prove valuable
for experiments.


You can respond by visiting:

SF email is sponsored by - The IT Product Guide
Read honest & candid reviews on hundreds of IT Products from real users.
Discover which products truly live up to the hype. Start reading now.
Boost-bugs mailing list

Boost list run by bdawes at, gregod at, cpdaniel at, john at