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.