Re: [Boost-Users] Johnsons BGL implementation for undirected graphs correct?

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-07-25 14:29:50

Hi Jan,

On Mon, 22 Jul 2002, Jan de Ruiter wrote:
yg-boo> When I use the BGL johnsons_all_pairs_shortest_paths example (source
yg-boo> below)on an undirected graph, some results are quite wrong.
yg-boo> For example, the output shows that the distance between node 1 and 6
yg-boo> equals 36. The SP however (1-4-5-8-9-6) = 4+4+4+12+2 = 26.
yg-boo> Is there something wrong with me or is the BGL implementation incorrect?
yg-boo> Any ideas?

Yes, that is a bug in the algorithm. Thanks for bringing this to my
attention. I've checked a new version with the fix into CVS. I've done a
little testing, but if you wouldn't mind checking it out and also
verifying that it works, I would thankful.

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]
----------------------------------------------------------------------