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++ による実装