This article of 2012 at http://stegua.github.io/ shows, that the type of the priority queue of a shortest path solver is crucial for the solving time.

You have to agree with that, but there is another point to mention: the choice of the graph representation.

I wanted to spend some more time on the comparison of the graph libraries LEMON and BGL and so I modified some of the code and ran the following tests on it.

The code was compiled using GCC 4.8.4 with the the following switches: -O2 -m64 -std=c++11. My test machine is a laptop with an Intel 4-Core i3@2,4 Ghz. You can download the graph instances from the DIMACS site.

**BGL’s Dijkstra d-ary Heap (d=4)**

Boost’s Graph Library offers two variants of a Dijkstra shortest path solver implementation. A regular one `dijkstra_shortest_path`

and a variant that does not use an internal color map of nodes (`dijkstra_shortest_path_no_color_map`

). Both of them use by default a d-ary Heap with d=4 which is in fact a quad heap queue. Unfortunately there is no easy way to change the heap in the dijkstra implementation.

There is no significant difference comparing the solving time of each of them, if you do not change the graph structure.

Using the BGL with street networks you have two options of a graphs: the widely known `adjacency_list`

and a representation that you should look at if you’re dealing with sparse graphs as street networks are: the `compressed_sparse_row_graph`

.

Here are the results.