ダイクストラ法

概要

最終更新日：2021/01/21

この記事は経路探索アルゴリズムの一つであるダイクストラ法について書いています。
主に次の項目に該当する方に向けて書いています。

サンプル

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


	
開発環境
	

		
VSのバージョン
		
VisualStudio 2019
	

ダイクストラ法とは

ダイクストラ法はグラフの２つのノードの最短経路を求めるアルゴリズムで、
ノードを主体として経路を割り出します。
同じ最短経路検出アルゴリズムであるベルマンフォード法と比較されますが、
ベルマンフォード法よりも高速に経路を検出することができます。
ただし、ダイクストラは負のコストが存在するグラフでの使用はできないようになっているため、、
そのようなグラフの場合はベルマンフォードを使用します。
※１．グラフの用語が使用されているのでノードや辺、隣接など聞き覚えのない方は
　こちらで確認していただければと思います。
※２．ノード間の重みは「コスト」で統一しています。

流れ

ダイクストラ法の最短経路検出の流れは以下の通りです。

この流れでは以下のグラフを使って説明をします。

①．始点ノードを決める

最初はグラフ内で探索を開始する始点ノードを決めます。
今回は以下のようにN:0を始点ノードとして扱いたいと思います。
※終点を決めるケースはこの記事の後半で説明しています。

②．探索状況を把握するための準備をする

次は経路探索の状況を把握するための準備を行います。
ダイクストラは始点ノードを基点として、隣接しているノードを次々と移動していきながら
始点ノードから各ノードまでの最小累計コストを決定していきます。
そのような探索の中で、どれくらいのノードがコストが確定せずに残っているかなどの
探索状況を把握するためのデータを用意します。
今回、用意したデータは以下の内容です。

このデータをノードの数だけ用意します。
今回はノードが５つ存在するのでデータも５つ用意します。

③．各ノードの累計コストを初期化する

準備が終わったら、各ノードの累計コストを初期化します。
②のデータでもありますが、探索時の各ノードは始点のノードから自分に到達するまでの
経路の累計コストを保持できるようにします。

そして、探索を始める前にその累計コストは初期化する必要があります。
この累計コストは経路の最小コストを保持するようになっており、初期化の際の初期値は小さい値は使用せず、
計算上で絶対にならないと確信が持てるほど大きい値を使用します。
こうすることで、最初の比較の際に必ず更新の必要があると判断することが出来ます。

※１．図では最大値は「∞」を使用しています。
※２．始点ノードだけはコストを「0」で初期化します。

④．探索データを全て未確定としてリスト化する

ここまでが探索開始までの準備となります。
探索データを以下のようにコスト未確定として管理できるようにまとめます。
ダイクストラではこのリストが空になったら全てのノードの最小コストが判明していることになります。



次の⑤では、このリストの最小コストを取得する必要があるため、コストで昇順ソートを行うか、
最小のコストを取得できるような関数を用意するなどして下さい。

⑤．未確定リストからノードを取り出す

ここから本格的に探索が開始されます。
まずは未確定のノードリストからノードを一つ取得します。
この時のポイントは以下の３つです。

上のポイントであるように、まずは未確定リストの中の最小コストであるN:0を取得します。
その後、未確定リストから取得したノードであるN:0を除外します。
最後に、取得したノードを最小コストが確定したノードとして扱います。

取得ノードが最小コストとして確定する理由

理由は次の3点です。

ダイクストラは始点から探索を開始しており、その後は未確定リストの中の最小コストのノードが優先されます。
そして、コストに負の値を使わないようにすることで累計コストを必ず増加させるようにします。



上のグラフでN:0を始点とした場合、最もコストが少ないのはコストが1のN:1へ移動する事です。
そのため、ダイクストラではN:1の最小コストが「1」であることが確定します。
N:2からもN:1への経路がありますが、N:0 => N:2 => N:1へ移動した場合のコストは3なので、
N:0 => N:1のコストを上回っていることが分かります。

このように遠回りの経路があったとしても、最小コストが確定したノードを新しい経路の累計コストが
下回ることはありません。

⑥．隣接ノードまでのコストを算出して既存のコストと比較する

取得したノードの隣接ノードを使い、新しい経路を探します。
その際に、隣接ノードへ移動する際の累計コストも新しく算出します。
算出式は以下の通り、非常に単純です。

新しい累計コスト = 取得したノードの累計コスト + 隣接ノードへ移動するためのコスト
N:0の隣接ノードであるN:1とN:3の累計コストは「0 + 1」で「1」、N:3は「0 + 2」で「2」となります。
現状では計算してコストを求めただけで、ノードへの更新はしません。


新しい累計コストを求めたら、以下のように隣接ノードに保存されている累計コストと比較します。

新しい累計コスト < 隣接ノードの累計コスト
比較の結果通り、新しい累計コストの方が小さかった場合は次のことを行います。

今回、N:1、N3の新しい累計コストは∞よりも小さいため、比較の条件を満たしているので、
以下の図のようなコスト更新が行われます。
そして、更新の際は隣接ノードに至ったノード(今回はN:0)の保存も行います。
これは経路を復元する際に必須となるので必ず保存してください。
また、⑤で最小コスト取得をしやすくしたい場合はリストのソートも行います。

⑦．全てのノードコストが確定するまで⑤と⑥を繰り返す

未確定リストにノードが残っている場合、探索が終了していないため、
リストが空になるまで、⑤と⑥を繰り返します。
例で見せているグラフを最後まで進めると以下のようになります。



N:0から各ノードまでの最小コストは以下の通りになりました。



これがダイクストラによる経路探索の流れです。

実装方法

サンプルの一部を使って実装方法を説明したいと思います。
※表示するコード量を少なくするために一部コードを削っています。
まずは経路の始点を決めます。(①)

void Graph::Dijkstra(int start_)
上記のコードのようにDijkstra関数の引数で始点を決めています。
次は探索状況を把握するためのデータの準備を行いますが、
データのインスタンス化の際に累計コストの初期化も合わせて行っています。(②と③)

// 探索用ノード
struct SearchNode
{
	SearchNode(Node* current, int cost) :
		currentNode(current),
		prevNode(nullptr),
		isConfirmed(false),
		totalCost(cost)
	{}

	Node* currentNode;
	Node* prevNode;

	int totalCost;
	bool isConfirmed;
};

size_t node_num = nodes.size();
std::vector search_nodes;
for (int i = 0; i < node_num; i++)
{
	Node* node = searchNode(i);
	int cost = Infinity;
	if (i == start_)
	{
		cost = 0;
	}

	// 探索用ノード作成とコスト初期化
	search_nodes.push_back(new SearchNode(node, cost));
}

準備処理の最後に②で作成した探索データを全てコストが未確定のノードとして扱います。(④)

for (int i = 0; i < node_num; i++)
{
	// 未確定ノードとして追加
	unsettled_nodes.push(SearchPair(search_nodes[i]->totalCost, search_nodes[i]));
}

ここまでがダイクストラを開始するための準備部分で、これ以降が実際の経路探処理になります。
まずは未確定リストからノードを取得します。
取得するノードは必ずリストの中で最小コストのノードを選択してください。
その後、取得したノードはリストから削除し、最小コストが確定したノードとして扱います。(⑤)

// 未確定リストから先頭ノードを取得
SearchPair data = unsettled_nodes.top();
// 先頭の削除
unsettled_nodes.pop();

if (data.second->isConfirmed == false)
{
	// 最小コストとして確定
	data.second->isConfirmed = true;
}
else
{
	// 確定しているので調べる必要なし
	continue;
}

取得したノードの隣接ノードまでのコストを算出して隣接ノードの保持するコストと比較します。
比較の結果、新しいコストが隣接ノードのコストを下回ったら、コストと経路情報の更新を行い
未確定リストのソートを行います(⑥)
※ソートのタイミングは必ずしもここでなくとも構いません。

int total_cost = data.first;
Node* search_node = data.second->currentNode;

// 未確定ノードの隣接ノードの更新が必要かどうかを判断する
for (int i = 0; i < search_node->GetEdgeNum(); i++)
{
	const Node::Edge* edge = search_node->GetEdge(i);
	Node* adjacent_node = edge->adjacentNode;

	// 最小コストが決定しているNodeは無視
	if (search_nodes[adjacent_node->GetId()]->isConfirmed == true)
	{
		continue;
	}

	int new_cost = total_cost + edge->cost;
	/*
		「今のノードまでのコスト + 隣接ノードまでのコスト」が
		　保存されている最小コストよりも小さければ更新する
	*/
	if (new_cost < search_nodes[adjacent_node->GetId()]->totalCost)
	{
		// 最小コストを更新する
		search_nodes[adjacent_node->GetId()]->totalCost = new_cost;

		// 更新したノードの経路となったノードを記録する
		search_nodes[adjacent_node->GetId()]->prevNode = search_node;

		/*
			ノード追加について
				priority_queueは要素の再ソートが任意で行えないため、
				SearchPairのtotalCostを変更しても再ソートが行われない
				そのため、costをキーとしたPairを作成して、データが増えるのを覚悟で
				新しいペアとしてプッシュして使わないデータは即座にcontinueする方法をとっている
		*/
		unsettled_nodes.push(SearchPair(new_cost, search_nodes[adjacent_node->GetId()]));
	}
}

最後に未確定のノードがある限り繰り返す処理を追加します。(⑦)

// 未確定ノードがなくなるまで続ける
while (unsettled_nodes.empty() == false)
{

	// ⑤と⑥のコードがそのまま入っている
}

これでダイクストラの実装が完了しました。
whileを抜けた後のsearch_nodesの各要素には「start_」ノードからの最小コストと、
そのノードを更新したノードの情報が保存されています。

for (int i = 0; i < node_num; i++)
{
	if (start_ == i)
	{
		continue;
	}

	printf("Node:%dからNod:e%dまでの最小コストは%d\n\n", start_, i, search_nodes[i]->totalCost);
}

// 出力結果：
Node:0からNode:1までの最小コストは1
Node:0からNode:2までの最小コストは5
Node:0からNode:3までの最小コストは2
Node:0からNode:4までの最小コストは4

経路復元

実装方法は最小コストを検出する内容になっていますが、最短経路を辿る方法には触れていないため、
ここではその方法について説明をしていきます。
探索用データには最小コストを更新した経路の一つ前のノードが保存されています。
経路復元は目的のノードのから更新したノード情報をトレースしていけば経路を求めることができます。


上の図の各ノードの最後にコストの更新を行ったノードは次の通りです。


	

		
ノード番号
		
　0　
		
　1　
		
　2　
		
　3　
		
　4　
	
	

		
更新したノード
		
　なし　
		
　0　
		
　4　
		
　0　
		
　3　
	

この表の中から終点を決めて更新したノードをたどっていけば始点であるN:0に到達します。
例えばN:2からN:0までの最短経路を辿る場合、以下の経路になります。

2 => 4 => 3 => 0
この経路の累積コストは5となるため、N:0～N:2までの最小コストと一致します。

実装方法

経路復元をプログラムで実装する方法はダイクストラ終了時にトレース処理を追加するだけです。
今回は全ての経路を出力するようにしています。

// 全ルート検出
for (int i = 0; i < node_num; i++)
{
	if (start_ == i)
	{
		continue;
	}

	printf("Start:%d => Goal:%d\n", start_, i);
	// 最短ルートを取得
	Node* current_route = searchNode(i);	// 今チェック中の経路ID
	std::list shortest_route;				// 経路保存用
	shortest_route.push_front(i);

	while (true)
	{
		if (current_route == nullptr ||
			search_nodes[current_route->GetId()]->prevNode == nullptr)
		{
			break;
		}
		// 次のノードを取得する
		Node* next_route = search_nodes[current_route->GetId()]->prevNode;
		shortest_route.push_front(next_route->GetId());

		// 始点じゃなかったら追加
		if (next_route->GetId() != start_)
		{
			current_route = next_route;
		}
		else
		{
			break;
		}
	}

	printf("最短ルートは");
	for (int id : shortest_route)
	{
		printf("%d ", id);
		printf("\n");
	}
}

// 出力結果
Start:0 => Goal:1
        最短ルートは0 1
Start:0 => Goal:2
        最短ルートは0 3 4 2
Start:0 => Goal:3
        最短ルートは0 3
Start:0 => Goal:4
        最短ルートは0 3 4

ダイクストラによって求められた開始ノードから各ノードまでの最短経路が出力されています。
これで経路復元も完了です。

終点指定

これまで説明したダイクストラの方法は開始ノードから全てのノードの最小コストと最短経路を求める内容でした。
しかし、全てではなく終点のノードを指定して、そこまでの最短経路を求めたい場合もあります。
ここではそのような場合にどのように改良したらよいかの説明をします。
といっても、やることは簡単で以下の内容を実装するだけです。

終点の指定

まずはダイクストラを実行する際に始点だけではなく、終点の指定も行います。
今回のサンプルでは、新しくDijkstra02という関数を作成し、そこで終点指定版のコードを実装しています。
※ほとんどのコードがDijkstraと同じです。

void Graph::Dijkstra02(int start_, int goal_)

終点ノードの最小コスト確定で探索打ち切り

終点ノードが判明したら、あとは終点ノードの最小コストが確定したら探索を終わらせれば実装完了です。

if (data.second->isConfirmed == false)
{
	// 最小コストとして確定
	data.second->isConfirmed = true;

	// Goalノードの最小コストが確定したので探索終了
	if (data.second->currentNode->GetId() == goal_)
	{
		break;
	}
}
else
{
	// 確定しているので調べる必要なし
	continue;
}

途中で打ち切っても問題ない事の証明

ダイクストラは始点ノードから最もコストがかからないノードが決まっていくようになっています。
そのため、終点と決めたノードの最小コストが確定した後に、そのノードが更新されることはありません。
以下のようにいくつかのグラフで終点で打ち切った場合と最後まで探索した場合の
コストと最短経路を比較してみます。



このように、終点が判明した時点で探索を打ち切っても、終点までのノードの最小コストに変化がないため、
発見次第打ち切っても問題ないことが分かります。
処理コストを考えると終点が分かっている場合は早々に探索を打ち切るのは有効な手段だといえます。