Re: [Boost-Users] BGL: dijkstra_shortest_paths and parallel edges

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-08-06 10:57:46

Hi Michael,

On Mon, 5 Aug 2002, Michael Kettner wrote:
kettne> Hi,
kettne>
kettne> my former posting leads me to another question:
kettne>
kettne> How does the dijkstra_shortest_paths behave if applied to a multigraph?

dijkstra's is based on BFS, which traverses the graph using out-edge
iterators, and out-edge iterators traverse all out-edges of a vertex,
including the parallel ones. Therefore, I think dijkstra's will behave
correctly for a multigraph.

kettne> And how does the dijkstra_shortest_paths behave if applied to a
kettne> filtered_(multi)graph containing parallel edges, but with only _one_ of the
kettne> parallel edges visible respectively?

That should be OK too.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------