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>)’
That's what the problem is... I couldn't see it. You can't instantiate a template over the type of a variable length array. You can probably think of it as a local type (a struct within a function), but it probably goes beyond that. Last time I checked, calling typeid on e.g., D resulted in a compiler error. That may have been GCC 4.1, though. Didn't GCC drop them at some point?
This holds for linear arrays also. One more argument against variable length arrays.