Re: [Boost-users] BGL, shortest path between two nearby nodes in a huge graph

Subject: Re: [Boost-users] BGL, shortest path between two nearby nodes in a huge graph
From: alex (alexhighviz_at_[hidden])
Date: 2016-01-21 04:06:46

> 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 <class Graph, class SourceInputIter, class DijkstraVisitor,
            class PredecessorMap, class DistanceMap,
            class WeightMap, class IndexMap, class Compare, class Combine,
            class DistZero, class ColorMap>
  inline void
  dijkstra_shortest_paths_no_init
    (const Graph& g,
     SourceInputIter s_begin, SourceInputIter s_end,
     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
     IndexMap index_map,
     Compare compare, Combine combine, DistZero zero,
     DijkstraVisitor vis, ColorMap color)