Hi, I spent a lot of time to figure out what the problem was. But the reason why there is a problem is still not clear. I modified the johnson_all_pairs_shortest_paths example program to allow for non-constant graphs. The example prog contained std::vector < int >d(V, (std::numeric_limits < int >::max)()); int D[V][V]; johnson_all_pairs_shortest_paths(g, D, distance_map(&d[0])); with V being const int whose value is known at compile time. In my program this is obviously not the case, therefore I defined const int V(num_vertices(g)); std::vector < int >d(V, (std::numeric_limits < int >::max)()); int D[V][V]; johnson_all_pairs_shortest_paths(g, D, distance_map(&d[0])); But this didn't compile, I got the error error: no matching function for call to ‘johnson_all_pairs_shortest_paths(Graph&, int [(long int)V][(long int)V], boost::bgl_named_params<int*, boost::vertex_distance_t, boost::no_property>)’ However, it is possible to access elements of D as D[i][j], even if V isn't known at compile time. This is (according to what I read at http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/BasicMatrix.html ) the only constrained for D. Substituting int D[V][V] with vector<vector<int> > D(V,vector<int>(V)) solves the problem, but still why is there a problem in the first place? Ralf