Boost.Graph 最短単純路

辺に重みのないグラフから最短経路を求めると、「最短単純路」という通過する辺が最も少ない経路が得られます。
Boost.Graphのboost::dijkstra_shortest_paths()は重みのないグラフを与えるとコンパイルエラーになるので、辺の重みを全て1に設定することで代用できます。

#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.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, G, Z, N };
const std::string Names = "SABCDEFGZ";

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

    // 辺の重みは1
    const std::vector<int> weights(edges.size(), 1);

    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<Vertex> parents(boost::num_vertices(g));
    boost::dijkstra_shortest_paths(g, from,
                boost::predecessor_map(&parents[0]));

    // 経路なし
    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
D
G
Z

最短単純路の用途としては、たとえばソーシャルグラフから「Twitterで何回のRTで特定の情報に辿りつけたか」という情報を抽出するのに使えるそうです。