Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk