最短経路探索 (Boost Graph Library 利用でダイクストラ法)

こんにちは。
Boost Graph Library を使う最短経路探索の説明¹ を見つけたので、そのコードにカスタムな breadth-first-search visitor を付加してみました²。実行例で始点Tokyo 終点Osakaを与え、経路解 Tokyo -> Nagoya -> Osaka (525.5 km) を得ました。

$ g++ -std=c++11 -I/usr/local/include boost_dijkstra_shortest_paths.cpp
$ ./a.out 
number of (nodes, edges) in a graph = (4, 5)
(from, to) = (Tokyo, Osaka)
path-finding starts, and then finishes
shortest path found:
Tokyo -> Nagoya -> Osaka  (525.5 km)

boost_dijkstra_shortest_paths.cpp

# include <string>
# include <iostream>
# include <boost/graph/adjacency_list.hpp>
# include <boost/graph/dijkstra_shortest_paths.hpp>

struct VertexProperty {
    std::string label;
};

struct EdgeProperty {
    double distance; // in kilometers
};

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::directedS,
    VertexProperty,
    EdgeProperty
> graph_t;

typedef graph_t::edge_descriptor edge_t;
typedef graph_t::vertex_descriptor vertex_t;

class my_visitor : boost::default_bfs_visitor{
protected:
  vertex_t destination_vertex_m;
public:
  my_visitor(vertex_t destination_vertex_l)
    : destination_vertex_m(destination_vertex_l) {};
  void initialize_vertex(const vertex_t &s, const graph_t &g) const {}
  void discover_vertex(const vertex_t &s, const graph_t &g) const {}
  void examine_vertex(const vertex_t &s, const graph_t &g) const {}
  void examine_edge(const edge_t &e, const graph_t &g) const {}
  void edge_relaxed(const edge_t &e, const graph_t &g) const {}
  void edge_not_relaxed(const edge_t &e, const graph_t &g) const {}
  void finish_vertex(const vertex_t &s, const graph_t &g) const {
    if (destination_vertex_m == s)
      throw(2);
  }
};

struct path {
    int F, T;  // cities
    double distance; // in kilometers
};

enum { Tokyo, Nagoya, Osaka, Okayama };  // cities

graph_t make_graph() {
    graph_t g;
    std::vector<std::string> cities = {"Tokyo", "Nagoya", "Osaka", "Okayama"};
    std::vector<path> paths = {
        {Tokyo, Nagoya, 325.5},
        {Nagoya, Osaka, 200.0},
        {Nagoya, Osaka, 300.0},
        {Tokyo, Osaka, 600.0},
        {Osaka, Okayama, 100.0}
    };
    for (const auto& p : paths) {
        add_edge(p.F, p.T, {p.distance}, g);
    }
    for (int i = 0; i < num_vertices(g); i++) {
        g[i].label = cities[i];
    }
    return g;
}

std::deque<vertex_t> get_path(vertex_t from, vertex_t to, std::vector<vertex_t> parents) {
    std::deque<vertex_t> path;
    for (vertex_t v = to; ; v = parents[v]) {
        path.push_front(v);
        if (v == from) break;
    }
    return path;
}

void print_path(graph_t g, std::deque<vertex_t>& path, double distance_to) {
    for (const auto& v : path) {
        std::cout << g[v].label;
        if (v != path.back()) {std::cout << " -> ";}
    }
    std::cout << "  (" << distance_to << " km)" << '\n';
}

void shortest_path(graph_t g, vertex_t from, vertex_t to) {
    my_visitor vis(to);
    std::vector<vertex_t> parents(num_vertices(g));
    std::vector<double> distance(num_vertices(g));
    try {
        std::cout << "path-finding starts";
        boost::dijkstra_shortest_paths(g, from,
            boost::weight_map(boost::get(&EdgeProperty::distance, g)).
                  predecessor_map(&parents[0]).
                  distance_map(&distance[0]).
                  visitor(vis)
        );
    }
    catch (int exception) {
        std::cout << ", and then finishes";
    }
    std::cout << '\n';

    if (parents[to] == to) {
        std::cout << "no solultion found" << '\n';
    } else {
        std::cout << "shortest path found:" << '\n';
        std::deque<vertex_t> path = get_path(from, to, parents);
        print_path(g, path, distance[to]);
    }
}

int main()
{
    graph_t g = make_graph();
    std::cout << "number of (nodes, edges) in a graph = (" << num_vertices(g);
    std::cout << ", " << num_edges(g) << ")\n";

    vertex_t from = Tokyo, to = Osaka;
    std::cout << "(from, to) = (" << g[from].label << ", " << g[to].label << ")\n";

    shortest_path(g, from, to);
}

1. ここの説明の中の dijkstra_shortest_paths を利用した最短経路探索です（「任意のクラスをプロパティにする」以降の箇所）。 ↩

2. 本記事ではadjacency_list 設定で VertexListS = vecS と指定したおかげで make_graph() 内で省力化できています。なお VertexListS = listS としたい場合の参考情報は、libs/graph/example/dijkstra-example-listS.cpp。 ↩