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

Subject: Re: [boost] How to speed up the djikstra graph
From: Lennart Berg (LB_at_[hidden])
Date: 2009-06-23 15:37:25

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_at_[hidden] [mailto:boost-bounces_at_[hidden]]
On Behalf Of Jeremiah Willcock
Sent: 23. juni 2009 15:42
To: boost_at_[hidden]
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