Boost.Graph 全頂点間最短距離を求める

Boost.Graphの最短経路アルゴリズムのひとつであるjohnson_all_pairs_shortest_paths()は、全ての頂点間の最短距離を計算します。
以下のグラフに対して、このアルゴリズムを適用してみます：

#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <iomanip>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/johnson_all_pairs_shortest.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
    boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef std::pair<int, int>                             Edge;
typedef boost::graph_traits<Graph>::vertex_descriptor   Vertex;

enum { S, A, B, C, D, E, F, Z, N };
const std::string names = "SABCDEFZ";

// グラフを作る
Graph make_graph()
{
    const std::vector<Edge> edges = {
        {S, A},
        {A, B},
        {B, C},
        {B, D},
        {C, E},
        {C, F},
        {D, F},
        {E, D},
        {F, E},
        {E, Z},
        {F, Z}
    };

    const std::vector<int> weights = {
        {3},
        {1},
        {2},
        {3},
        {7},
        {12},
        {2},
        {11},
        {3},
        {2},
        {2}
    };

    return Graph(edges.begin(), edges.end(), weights.begin(), N);
}

template <class DistanceMatrix>
void print(const DistanceMatrix& mat, int num_vertices, const std::string& name_map)
{
    std::cout << "       ";
    for (int k = 0; k < num_vertices; ++k) {
        std::cout << std::setw(5) << name_map[k];
    }
    std::cout << std::endl;
    for (int i = 0; i < num_vertices; ++i) {
        std::cout << std::setw(3) << name_map[i] << " -> ";
        for (int j = 0; j < num_vertices; ++j) {
            if (mat[i][j] == (std::numeric_limits<int>::max)())
                std::cout << std::setw(5) << "inf";
            else
                std::cout << std::setw(5) << mat[i][j];
        }
        std::cout << std::endl;
    }
}

int main()
{
    const Graph g = make_graph();

    std::vector<int> d(N, (std::numeric_limits<int>::max)());
    int distance_mat[N][N];
    boost::johnson_all_pairs_shortest_paths(
            g, distance_mat, boost::distance_map(d.data()));

    print(distance_mat, N, names);
}

           S    A    B    C    D    E    F    Z
  S ->     0    3    4    6    7   12    9   11
  A ->   inf    0    1    3    4    9    6    8
  B ->   inf  inf    0    2    3    8    5    7
  C ->   inf  inf  inf    0   18    7   12    9
  D ->   inf  inf  inf  inf    0    5    2    4
  E ->   inf  inf  inf  inf   11    0   13    2
  F ->   inf  inf  inf  inf   14    3    0    2
  Z ->   inf  inf  inf  inf  inf  inf  inf    0

全ての頂点から全ての頂点への最短距離の行列(2次元配列)ができました。
ここでのグラフは有向なので、ある頂点からは到達できない頂点が発生します。そういった場合には、デフォルトでnumeric_limits<辺の重さ型>::max()値が入ります。

私が調べた限りでは、このアルゴリズムは距離しかわからないようです。経路はとれないみたいですね。
内部的にはbellman_ford_shortest_paths()とdijkstra_shortest_paths()を実行してるので、原理的にはできるのでしょうけど、Visitorが指定できないみたいなのでなんとも・・・。

参照：
johnson_all_pairs_shortest_paths - Boost Graph Library
全点対間最短路 (Johnson) - 各種アルゴリズムの C++ による実装