読者です 読者をやめる 読者になる 読者になる

Boost.Graph DistanceMap

C++

最短経路の計算時に使用する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」の距離になってるはずです。