Re: [Boost-users] Dijkstra in a multi-graph (parallel edges)

From: Ioannis Nousias (s0238762_at_[hidden])
Date: 2008-04-01 18:37:11

moritz Hilger wrote:
>>  I'm using dijkstra_shortest_paths() in a multi-graph, which seems to
>>  work fine. Via the predecessor map I get the vertices in the shortest
>>  path. However, how do I get the edges of the shortest path, bearing in
>>  mind this is a multi-graph (has parallel edges)?
>>     
>
> Hi,
> you can scan all edges e connecting vertices u=pred(v) and v until you
> find one for which dist(v)-dist(u)=length(e) (use edge_range to get
> ALL edges connecting u and v). if you just need the length you don't
> even have to scan. Or you could fill a predecesor map with edges via a
> visitor hooked to edge_relax (see
> http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/DijkstraVisitor.html)
> hth,
> Moritz
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
>
>   
Hi Moritz,

I need to access an edge property from each edge within the shortest 
path. Finding the edges by scanning them might be costly (this is meant 
to be inside a very intensive portion of my algorithm). I was looking at 
Dijkstra's visitors' descriptions, but didn't understand them. So when 
is edge_relaxed() invoked ? Are those edges, for which edge_relaxed() is 
called, the ones with the shortest length?

thanks

-Ioannis

-- 
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.