Re: [Boost-users] Dijkstra with Fibonacci heaps

From: moritz Hilger (moritz.hilger_at_[hidden])
Date: 2007-09-13 10:47:56

> I want to solve a shortest path problem using the Dijkstra algorithm with
> Fibonacci heaps.  The particular aspect of the problem is that the labels
> associated to the vertices other than the source are not infinity.  The
> labels are different each time the Dijkstra procedure is called.

Hi, Dijkstra's algorithm is implemented in the boost graph library (BGL,
http://www.boost.org/libs/graph/doc/). See
http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html for
details.
The default implementation uses an implementation of an Relaxed heap
(similiar to Fibonnaci heaps) as priority queue. The algorithm takes  as
parameter (among others) a data structure for storing the distances. You can
initialize this prior to execution and call dijkstra_shortest_paths_no_init
to avoid setting all labels to infinity.

hth
Moritz

-- 
Moritz Hilger
Combinatorial Optimization & Graph Algorithms
TU Berlin
[phone]