johnson algorithm, bug or feature?

I have tested the johnson_all_pairs_shortest_paths example of 
libboost-graph 1.28. It's a directed graph. Shortest path from vertex 3 
to vertex 0 weights "inf" (all edges of vertex 0 are outgoing edges). 
That's OK.

Now we change the graph from directedS to undirectedS. The path weights 
now "5":

         0    1    2    3    4    5
0 ->    0    0    -1    -5    0    -4
1 ->    0    0    -1    -5    0    -4
2 ->    1    1    0    -4    1    -3
3 ->    5    5    4    0    5    1
4 ->    0    0    -1    -5    0    -4
5 ->    4    4    3    -1    4    0

But if the path is 3-> 4 -> 0, should it not be "-5"? Why does the 
algorithm change the sign in an undirected graph?

In this reference of NIST
http://www.nist.gov/dads/HTML/johnsonsAlgorithm.html
we can read:

"Johnson's algorithm

(algorithm)

Definition: An algorithm to solve the all pairs shortest path problem in 
a sparse weighted, directed graph".

So, is it really the problem that Johnson's algorithm doesn't work on 
undirected graphs? If so, shouldn't the function throw a compilation 
error/warning and/or be warned in the documentation?

Regards,

Ramón.




------------------------ Yahoo! Groups Sponsor ---------------------~-->
Get 128 Bit SSL Encryption!
http://us.click.yahoo.com/CBxunD/vN2EAA/xGHJAA/EbFolB/TM
---------------------------------------------------------------------~->

Info: <http://www.boost.org>
Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
Unsubscribe: <mailto:boost-users-unsubscribe@xxxxxxxxxxxxxxx>
 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/