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 +49 30 314-25773