
Boost : 
Subject: Re: [boost] How to speed up the djikstra graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20090623 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk