Re: [Boost-Users] dijkstra_shortest_paths with undirectedS example

From: Michael Kettner (kettner_at_[hidden])
Date: 2003-04-22 09:15:04

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

Hi,

> The result is :
> distances and parents:
> distance(0) = 0, parent(0) = 0
> distance(1) = 2, parent(1) = 0
> distance(0) = 1, parent(2) = 0

According to your code, the last line should be
 distance(2) = 1, parent(2) = 0
Thr results are all correct. Why did you expect them to be different? You have 
an undirected Graph, and you can directly reach node 1 and 2 from node 0:

> min paths tree
> 0 -> 1 2
> 1 ->
> 2 ->

> I think the correct one should be:
> distances and parents:
> distance(0) = 0, parent(0) = 0
> distance(1) = 2, parent(1) = 2

Why that? Node 1 is directly connected with node 0 and the path via node 2 is 
not shorter.

> distance(2) = 1, parent(2) = 0
> min paths tree
> 0 -> 1
> 1 -> 2

Here again: see above.

> 2 ->

Michael

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

iD8DBQE+pU5pkCdGnb0kVFMRAsOiAKCB5OfzNHHux/kj9M92h4TnFLSL3gCfdegJ
QpU7QJwOU88UONIDHLgaumI=
=qxUV
-----END PGP SIGNATURE-----