Boost.Graph DistanceMap
最短経路の計算時に使用するDistanceMapは、開始地点から頂点vまでの距離を表すデータです。
distance_map[v]とすると、開始地点から頂点vまでの「最短経路の辺の重みの和」としての距離が取得できます。
先日の「Boost.Graph PredecessorMap」のエントリで使用したグラフで、最短経路の距離を計算してみましょう。
SからZまでの距離は以下のようにして計算します:
#include <iostream> #include <vector> #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/assign/list_of.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 = boost::assign::list_of<Edge> (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 = boost::assign::list_of (3) (1) (2) (3) (7) (12) (2) (11) (3) (2) (2) ; return Graph(edges.begin(), edges.end(), weights.begin(), N); } int main() { const Graph g = make_graph(); const Vertex from = S; // 開始地点 const Vertex to = Z; // 目的地 // 最短経路を計算 std::vector<std::size_t> distance(boost::num_vertices(g)); boost::dijkstra_shortest_paths(g, from, boost::distance_map(&distance[0])); // 目的地までの距離を取得 const std::size_t d = distance[to]; std::cout << d << std::endl; }
11
最短経路「S -> A -> B -> D -> F -> Z」の距離になってるはずです。