Dear list,
I am a happy user of BGL, but recently I got stuck in a strange problem. I think I am missing the obvious, so I'll be happy to read the fine manual if it's the case. Just point me to the right direction.
I need to find the shortest path between two nodes, for doing so I am using dijkstra with a custom visitor that stops the search (throwing an exception) when examine_vertex is called on the destination node.
It worked fine, but it run strangely slow. After some profiling, it is clear that most of the time is used in the initialize_vertex function. The graph is fairly large, but the path I am looking for are fairly small (10 edges tops usually).
It is possible to skip the initialize phase?
There are a number of (undocumented) dijkstra_shortest_paths_no_init(...)
functions in dijkstra_shortest_paths.hpp. I think you need the one with the
signature listed below, because it is the only one that does not initialize
the color map.
A strategy can be to use a visitor to keep a list of all discovered vertices
and re-initialize those (predecessor, distance, color) after each path is
found.
// Call breadth first search
template