グラフアルゴリズムの使用方法：ダイクストラの最短パスアルゴリズム

グラフアルゴリズムの使用例としてダイクストラの最短パスを使う。以下サンプルコード

#include <iostream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/vector_property_map.hpp>
#include <boost/foreach.hpp>

using namespace std;
using namespace boost;

int main()
{
	typedef adjacency_list <
		vecS, vecS,
		undirectedS,
		no_property,
		property < edge_weight_t, int >
	> Graph;
	typedef graph_traits <Graph>::vertex_descriptor Vertex;
	typedef std::pair<int, int> E;

	const int num_nodes = 5;
	E edge_array[] = { E(0, 1), E(1, 2), E(0, 3), E(3, 4), E(0, 4), E(1, 3) };
	int weights[] = { 1, 2, 1, 2, 7, 3 };
	int num_edges = sizeof(edge_array) / sizeof(E);
	// 重みつきの辺を指定してグラフを初期化
	Graph g(edge_array, edge_array + num_edges, weights, num_nodes);

	Vertex s = vertex(0, g);	// 探索の始点
	vector_property_map<Vertex> p;	// 最短パスにおける各頂点の親を格納するためのプロパティマップ
	vector_property_map<int> d;	// 各頂点の最短パスの長さを格納するためのプロパティマップ
	// ダイクストラの最短パスアルゴリズムを呼ぶ
	dijkstra_shortest_paths(
		g,	// グラフ
		s,	// 始点
		predecessor_map(p).distance_map(d)	// 名前つき引数によるプロパティマップの指定
	);
	// 結果の出力
	std::cout << "頂点\t距離\t親" << std::endl;
	BOOST_FOREACH(const auto& v, vertices(g)) {
		cout << v << "\t" << d[v] << "\t" << p[v] << endl;
	}

	return 0;
}

結果

頂点    距離    親
0       0       0
1       1       0
2       3       1
3       1       0
4       3       3

• 上のサンプルコードでは名前付き引数を使ってアルゴリズムの出力を受け取るための外部プロパティマップを渡している。
• 名前付き引数の使い方
  • 引数名(渡す引数)を必要なだけ'.'(ピリオド)で繋げて指定する
• 外部プロパティマップとしてboost::vector_property_mapを使用
  • 参考サイト：Vector Property Map - 1.44.0
  • 以前外部プロパティマップとして用いたboost::iterator_property_mapは生成時に要素数が分かってないといけなかった。でもvector_property_mapの方はその制限がないので、結果を受け取るためのプロパティマップとしてより使いやすそう。