I think there is something I do not know, rather important, about the process of adding edges to the graph object. Infact, even in the simple libs/graph/example/bfs.cpp if I swap the start with the ends, I get different results. Namely: If I change the code from this boost::add_edge(0,2,G); boost::add_edge(1,1,G); boost::add_edge(3,1,G); ... boost::add_edge(4,1,G); to boost::add_edge(2,0,G); boost::add_edge(1,1,G); boost::add_edge(1,3,G); ... boost::add_edge(1,4,G); then I get the graph OK but the distances and the parent vectors are screwed: I get distances: 0 2 2 2 1 instead of distances: 0 2 1 2 2 and parent[0] = 0 parent[1] = 4 parent[2] = 4 parent[3] = 4 parent[4] = 0 instead of parent[0] = 0 parent[1] = 2 parent[2] = 0 parent[3] = 2 parent[4] = 2 I feel I am missing some basic knowledge on how to appropriately use this powerful and amazingly fast system. I would love to learn the missing bit. Looking forward your advice and sorry again for the dumminess of this question.