Mhh... I am a little confused. As I understand your post, dijstra recognizes "std::numeric_limits<Dist>::max" as beeing unreachable. That means that a graph like this: A-1-B-2-C-1-D-max-E-4-F-3-G Where StartVertex = A, will only have 4 ilterations, as we only have 4 edges on vertexes that are accessible. The rest will remain as MAX, as they have not been visited. Now is that correct, or does the djikstra graph go through ALL edges and vertices and just hit the limit on all edges after D-E. Or in short: Is the djikstra time static with a static mount of edges? Or does it recognize and shorten the search at inaccessible edges. -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: 23. juni 2009 15:42 To: boost@lists.boost.org Subject: Re: [boost] How to speed up the djikstra graph 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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost