ダイクストラ法


概要

ダイクストラ法はグラフの2頂点間の最短経路を求めるアルゴリズムで、
頂点を主体として経路を割り出します。
同じ最短経路検出アルゴリズムであるベルマンフォード法と比較されますが、
ベルマンフォード法よりも高速に経路を検出することができます。
※グラフの用語が使用されているので頂点や辺、隣接など聞き覚えのない方は
 こちらで確認していただければと思います。

サンプル

サンプルはここからダウンロードできます。
環境については以下の内容となっています。

開発環境
VSのバージョン
VisualStudio 2019

流れ

ダイクストラ法の最短経路検出の流れを以下のグラフで説明します。

algorithm_0029

①.始点と終点を決める

まずは経路の始点と終点を決めます。
今回は始点が頂点0、終点が頂点7のパスの最短経路を見つけます。

algorithm_0030

②.経路の距離を初期化する

始点と終点を決めたら次は各頂点までの距離を初期化します。
初期値は最短を求めるので小さい値は使用せず、
距離計算上で絶対にならないと確信が持てるほど大きい値を使用します。
※図では「∞」を使用しています。

algorithm_0031

③.始点と隣接している頂点までの距離をはかる

初期化が終了したら始点と隣接してる頂点に対し、
以下の条件式を使用して頂点間の最短距離を調査を行います。
条件が成立ていたら隣接先の頂点の最短距離を更新します。

基点となる頂点の最短距離 + 隣接先の頂点に到達するためのコスト < 隣接先の頂点の最短距離
例として頂点0と頂点2の2頂点間の調査を行います。
必要となる情報は以下の通りです。

頂点:0 最短距離:0
頂点0 => 頂点2の辺 コスト:1
頂点:2 最短距離:∞
この情報を式にあてはめます。 0 + 1 < ∞ 条件は成立しているので頂点2の最短距離を基点の最短距離 + コストの値で更新します。 algorithm_0032 残りの隣接している頂点の最短距離の計測し、更新できるかを調べます。 algorithm_0039 このように各頂点で最大値を設定しておき、その値を最短距離に置き換えていくことを 「緩める」「緩和」と呼ばれています。

④.始点以外で最短距離が小さい頂点を調べる

始点に隣接している頂点までの最短距離を調べたら、次はそれらの頂点で
最も距離が小さい頂点を使用し、隣接している頂点間の距離を計測します。
今回対象となる頂点は「V2」「V3」「V4」で、この中で最も距離が
小さいのは「V2」なので、このV2を使用して調査を行います。

algorithm_0040

このV2から隣接している頂点「V1」に対し、③と同じやり方で距離の計測をします。

algorithm_0041

これでV2の調査が終了した時点で次の調査対象となる頂点は「V1」「V3」「V4」となり、
調査が終了したV2は調査対象から外します。

調査対象となる頂点ですが、「更新された場合のみ対象」となります。
更新が行われなかった場合は対象から外れるので注意してください。

⑤.「④」を調査対象の頂点がなくなるまで続ける

あとは、④を調査対象の頂点がなくなるまで続ければ
最終的に最短経路が検出されます。

algorithm_0034

実装方法

サンプルの一部を使って最短距離検出の説明したいと思います。
※コード量を少なくするために必要ではない部分は削っています。

最短経路検出は「流れ」の項目を実装するだけです。
まずは「①」の経路の始点と終点を決めます。

void Dijkstra(int start, int goal)

Dijkstra関数の引数で始点と終点を決めます。
次に「②」の始点と始点以外の頂点の最短距離の初期化を行います。

int distances[NodeNum];					// 各頂点の最短距離保存用配列
std::fill(distances, distances + NodeNum, Infinity);	// 未計測状態として初期化
distances[start] = 0;					// 探索開始位置として初期化

初期化が完了したら「④」の候補となっている頂点と
隣接している頂点の最短距離を調査します。
(③は④の一部として扱います)

/*
	計測候補キューの先頭から頂点を取得
	この頂点が始点、保存されてる各辺に登録されている
	頂点が終点として計測を行う
*/
Pair node = survey_node_que.top();
// 先頭の削除
survey_node_que.pop();

ShortestDistance distance = node.first;
NodeId node_id = node.second;

/*
	計測対象の頂点までの最短距離(p.first)が
	その頂点に至るまでの最短距離(distances[node_id])よりも
	遠いなら次の頂点を探さない
*/
if (distances[node_id] < distance)
{
	continue;
}

// 測量用頂点の辺の数だけ調べる
for (int i = 0; i < g_Nodes[node_id].size(); i++)
{
	Edge edge = g_Nodes[node_id][i];
	/*
		今の頂点までの距離 + 辺のコストが
		保存されている次の頂点までの最短距離よりも近ければ更新する
	*/
	if (distances[node_id] + edge.Cost < distances[edge.ToNodeId])
	{
		// 更新した経路の始点側の頂点IDを記録する
		last_update_node_ids[edge.ToNodeId] = node_id;

		// 最短距離を更新する
		distances[edge.ToNodeId] = distances[node_id] + edge.Cost;
		// 次の測量候補として登録する
		survey_node_que.push(Pair(distances[edge.ToNodeId], edge.ToNodeId));
	}
}

最後に候補となっている頂点がある限り繰り返す処理を追加します。

while (survey_node_que.empty() == false)
{
	// すぐ上のコードがそのまま入っている
}

これでダイクストラの実装が完了しました。
whileを抜けた後のdistancesのgoal番目にはstart番目の頂点からの
最短距離が格納されています。

printf("最短距離は%d\n", distances[goal]);

実行結果:
	最短距離は8

経路復元

上の説明は最短距離を検出する内容になっていますが、
最短経路には触れていないので、どの経路で行けば最短になるのか分かりません。
最短経路を調べるためには各頂点の最短距離を更新した頂点の番号を保存します。

algorithm_0034
上の図の各頂点の最後に距離の更新を行った頂点は次の通りです。

頂点番号  0   1   2   3   4   5   6   7 
更新した頂点番号  -1   2   0   0   0   1   4   5 
上の表を終点の頂点7から更新した頂点番号をたどっていけば 始点である0に到達します。 7 => 5 => 1 => 2 => 0 この方法をプログラムで実装する場合、最短距離を更新した頂点番号を 保存する配列を頂点の数だけ用意して、更新時に保存していきます。 int last_update_node_ids[NodeNum]; // 各頂点距離の最後に変更した頂点ID保存用 std::fill(last_update_node_ids, last_update_node_ids + NodeNum, Infinity); // 未計測状態として初期化 last_update_node_ids[start] = -1; int distances[NodeNum]; // 各頂点の最短距離保存用配列 std::fill(distances, distances + NodeNum, Infinity); // 未計測状態として初期化 distances[start] = 0; // 探索開始位置として初期化 /* 計測候補頂点保存用のキュー 優先順位は最短距離が最も高く、同じ場合は頂点番号の小さい方とする 優先順位付きキュー Pairを使った場合ソートはfirstを基準に行う firstが同じ値の場合はsecondでソートされる */ std::priority_queue< Pair, // 要素はPair<int, int> std::vector<Pair>, // コンテナの型 vectorを使用 std::greater<Pair> // 昇順でソートする(ソート方法の自作可能) > survey_node_que; // 計測候補頂点として指定された頂点を指定 survey_node_que.push(Pair(0, start)); while (survey_node_que.empty() == false) { /* 計測候補キューの先頭から頂点を取得 この頂点が始点、保存されてる各辺に登録されている 頂点が終点として測量を行う */ Pair node = survey_node_que.top(); // 先頭の削除 survey_node_que.pop(); ShortestDistance distance = node.first; NodeId node_id = node.second; /* 計測対象の頂点までの最短距離(p.first)が その頂点に至るまでの最短距離(distances[node_id])よりも 遠いなら次の頂点を探さない */ if (distances[node_id] < distance) { continue; } // 測量用頂点の辺の数だけ調べる for (int i = 0; i < g_Nodes[node_id].size(); i++) { Edge edge = g_Nodes[node_id][i]; /* 今の頂点までの距離 + 辺のコストが 保存されている次の頂点までの最短距離よりも近ければ更新する */ if (distances[node_id] + edge.Cost < distances[edge.ToNodeId]) { // 更新した経路の始点側の頂点IDを記録する last_update_node_ids[edge.ToNodeId] = node_id; // 最短距離を更新する distances[edge.ToNodeId] = distances[node_id] + edge.Cost; // 次の測量候補として登録する survey_node_que.push(Pair(distances[edge.ToNodeId], edge.ToNodeId)); } } } 更新した頂点IDの配列が完成したらlistなどの機能を使用して、 終点の頂点IDから順番に始点までの頂点IDを保存していきます。 // 最短ルートを取得 int current_route_id = goal; // 今チェック中の経路ID std::list<int> shortest_route; // 経路保存用 shortest_route.push_front(goal); while (true) { // 頂点配列から次の頂点IDを取得する int next_id = last_update_node_ids[current_route_id]; // 始点じゃなかったら追加 if (current_route_id != start) { shortest_route.push_front(next_id); current_route_id = next_id; } else { break; } } これで作成したリストから最短経路がわかります。 printf("最短ルートは"); for (int id : shortest_route) { printf("%d ", id); } 実行結果: 0 => 2 => 1 => 5 => 7 これでダイクストラ法による最短経路検出が完成しました。