Yes, but there are better solutions than running N * (N+1)/2 times Dijkstra... (google All Pairs Shortest Path Problem)

I'd be surprised if the boost library has not all the required functionality. It's probably just not implemented in the Perl bindings. If speed is an issue, then maybe just use the C++ library directly, otherwise try Graph as suggested.

Update: Graph also returns a "random" shortest graph.