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

[Ioannis Nousias]

Hello,

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)?

thanks
Ioannis

PS: is this the right mailing list to ask these sort of questions ?

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

_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[moritz Hilger]

> 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

[Ioannis Nousias]

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.

_______________________________________________