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

From: Michael Kettner (kettner_at_[hidden])
Date: 2002-07-23 04:03:45

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Jan,

as far as I can see the distance between node 9 and node 6 equals 12 and not 2 
as you are assuming. So the result is 4+4+4+12+12 = 36 which is perfectly 
correct.

Michael

On Monday 22 July 2002 10:30, Jan de Ruiter wrote:
> When I use the BGL johnsons_all_pairs_shortest_paths example (source
> below)on an undirected graph, some results are quite wrong.
> For example, the output shows that the distance between node 1 and 6
> equals 36. The SP however (1-4-5-8-9-6) = 4+4+4+12+2 = 26.
> Is there something wrong with me or is the BGL implementation incorrect?
> Any ideas?
>
> Jan de Ruiter
>
>
> //Output
>            0    1    2    3    4    5    6    7    8    9
>       0    0   99  111  123  103  107  135  105  111  123
>       1  -99    0   12   24    4    8   36    6   12   24
>       2 -111  -12    0   12   -8   -4   24   -6    0   12
>       3 -123  -24  -12    0  -20  -16   12  -18  -12    0
>       4 -103   -4    8   20    0    4   32    2    8   20
>       5 -107   -8    4   16   -4    0   28   -2    4   16
>       6 -135  -36  -24  -12  -32  -28    0  -30  -24  -12
>       7 -105   -6    6   18   -2    2   30    0    6   18
>       8 -111  -12    0   12   -8   -4   24   -6    0   12
>       9 -123  -24  -12    0  -20  -16   12  -18  -12    0
>

[snipped]

- -- 
Dipl.-Ing. Michael Kettner, Wissenschaftlicher Mitarbeiter
Institut für Verkehrswesen, Eisenbahnbau und -betrieb, Universitaet Hannover
Appelstr. 9A                   # Tel: ++49/(0)511/762-4273
D-30167 Hannover               # Fax: ++49/(0)511/762-3001
http://www.ive.uni-hannover.de # kettner_at_[hidden]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE9PRvxkCdGnb0kVFMRAow7AJ0ejHg2pTtFMeFlz0vVvDhNN/e4ugCcD82W
iDetBOFHzpvFnTRRFnWoffY=
=QKvH
-----END PGP SIGNATURE-----