Boost.Graph 動的な辺の重みで最短経路探索する

グラフ型オブジェクトに直接設定されている辺の重みではなく、状況によって変化する重みを別のところから参照して、最短経路探索に使いたい場合があります。
そういう場合には、boost::function_property_mapというのを使います。やってみましょう。

#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/assign/list_of.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS> 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)
    ;

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

struct MyDynamicWeightFunctor {
    typedef int result_type;

    result_type operator()(boost::graph_traits<Graph>::edge_descriptor e) const {
        return 3; // 辺eの重みを返す
    }
};

int main()
{
    const Graph g = make_graph();
    const Vertex from = S; // 開始地点
    const Vertex to = Z; // 目的地


    MyDynamicWeightFunctor weight_functor;
    boost::function_property_map<
        MyDynamicWeightFunctor,
        boost::graph_traits<Graph>::edge_descriptor,
        int
    > weight_map(weight_functor);

    // 最短経路を計算
    std::vector<Vertex> parents(boost::num_vertices(g));
    boost::dijkstra_shortest_paths(g, from,
                boost::predecessor_map(&parents[0]).weight_map(weight_map));

    // 経路なし
    if (parents[to] == to) {
        std::cout << "no path" << std::endl;
        return 1;
    }

    // 最短経路の頂点リストを作成
    std::deque<Vertex> route;
    for (Vertex v = to; v != from; v = parents[v]) {
        route.push_front(v);
    }
    route.push_front(from);

    // 最短経路を出力
    for (const Vertex v : route) {
        std::cout << Names[v] << std::endl;
    }
}

S
A
B
C
F
Z

MyDynamicWeightFunctorという関数オブジェクトが、辺の重みを動的に取得して返します。
その関数オブジェクトの変数を作り、boost::function_property_mapで包み、最短経路アルゴリズムの名前付き引数weight_mapに渡すことで、最短経路アルゴリズム内で動的な辺の重みが使用されるようになります。

情報元：
Boost Graph Algorithm - Adding a constraint - StackOverflow
function_property_map - Boost Property Map Library