Re: [boost] How to speed up the djikstra graph

Subject: Re: [boost] How to speed up the djikstra graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-06-23 09:42:06

On Tue, 23 Jun 2009, Lennart Berg wrote:

(snip)
> Also is it possible (and would it be faster) to avoid creating a graph and
> calling add edge altogether and instead use a static graph with a visitor to
> determine edge cost, and if the edge is valid...
>
> I used the whole day yesterday to look for examples, but I couldn't find any
> using the boost library for that purpose.

I don't think you need a visitor.  You can change edge properties without 
changing the structure of the graph.  If you set the weight of an edge to 
infinity (using the distance_inf value that is passed into 
dijkstra_shortest_paths, which is usually 
(std::numeric_limits<Dist>::max)()), it is as though it doesn't exist in 
the graph for Dijkstra's algorithm.  You just need to check the output 
distance map for that value to determine if a vertex is unreachable.  If 
turning on and off edges in the graph is the only structure modification 
you need, that might be a good way.  Note that this saves you the add_edge 
cost, but Dijkstra will still need to traverse all of the edges including 
those that have infinite weight.

-- Jeremiah Willcock