Artikel getaggt mit ‘Benchmark’

Oktober 28th, 2016

Solving the Shortest Path Problem (5) – Benchmarks

This article of 2012 at 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 actually 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 flavours of a graph: 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.

weiterlesen »

Be the first to like.