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

From: moritz Hilger (moritz.hilger_at_[hidden])
Date: 2008-04-01 16:23:28

>  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