Opened 13 years ago

Closed 12 years ago

#379 closed Bugs (None)

Investigate other kinds of heaps for dijkstra_shortest_paths

Reported by: Douglas Gregor Owned by: Douglas Gregor
Milestone: Component: graph
Version: None Severity:
Keywords: Cc:


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. 

Attachments (0)

Change History (1)

comment:1 Changed 12 years ago by Douglas Gregor

Status: assignedclosed
Logged In: YES 

"The lore" seems to indicate that relaxed heaps are good enough. If we find 
performance problems later or someone codes a better priority queue, we'll 
consider it at that time.

Modify Ticket

Change Properties
Set your email in Preferences
as closed The owner will remain Douglas Gregor.
The resolution will be deleted.

Add Comment

E-mail address and name can be saved in the Preferences.

Note: See TracTickets for help on using tickets.