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@lists.boost.org 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.