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