ゲームの目的地までの最速経路を求める【ダイクストラ法】その2

前回の記事ではダイクストラ法のなんとなくのイメージを解説しました。

前回の記事ではルートの算出までは扱っていなかったので、今回は最小コストのルートを求める方法をざっくり解説します。

ダイクストラ法の流れに合わせてルートの算出を行います。

まず前回と同じグラフを考えます。

まずスタートノードを確定させます。コストは0です。

スタートノードの隣接ノードをチャレンジノード（緑）にします。

チャレンジノードにスタートノードからのコストと親として移動元のノードA（赤）を設定します。

チャレンジノードのうち、コストが最小となるノードBを確定させます。

直近の確定ノードから確定ノード以外の隣接ノード（ここではC）へチャレンジします。

コストがそれまでのコストより小さくなったら、小さいほうのコストでノードのコストを更新します。

また更新があったら、移動元のノードを親として更新します。今回はコストが変わらなかったので更新しません。

チャレンジノードのうち最小のコストとなるノードを確定します。今回はノードCです。

直近の確定ノードから確定ノード以外の隣接ノードへチャレンジします。CからD,E,Fへチャレンジします。

Cのコスト3から隣接ノードへのコストを加算したコストをD,E,Fに設定します。

チャレンジしたら移動元のノード（C）を親として設定します。

チャレンジノードのうち最小のコストとなるノード（D）を確定します。

直近の確定ノードから確定ノード以外の隣接ノード（F）へチャレンジします。

チャレンジノードのコストがそれまでのコストより小さくなったら、小さいほうのコストで更新します。

今回は小さくなったのでコストを7から6へ更新、Fの親をDで更新します。

チャレンジノードのうち最小コスト（E）のノードを確定します。

直近の確定ノードから確定ノード以外の隣接ノード（F,G）へチャレンジをします。

チャレンジしたノードのコストを、移動元のノードのコストにチャレンジノードへのコストを加算して算出します。

チャレンジノードのコストがそれまでのコストを下回るなら更新します。今回はE→Fは下回らないので更新しません。

チャレンジノードのうち最小コストになるノード（F）を確定します。

直近の確定ノード（F）から確定ノード以外の隣接ノード（G）へチャレンジします。

チャレンジノードのコストがそれまでのコストを下回れば、下回った方のコストで更新して、移動元のノードを親として設定します。

今回はGのコストが下回ったため、Gのコストを7で更新して、Gの親をFにします。

チャレンジノードのうちコストが最小のノード（G）を確定します。

チャレンジノードがなくなったので終了します。

さてここからがルートの算出です。

AからGまでのルートを算出します。

まずGをルートに追加します。Gの親はFなので、Fを参照します。

Fをルートに追加します。Fの親はDなのでDを参照します。

Dをルートに追加します。Dの親はCなのでCを参照します。

Cをルートに追加します。Cの親はAなのでAを参照します。

Aをルートに追加します。スタートノードへ到達したのでルートの算出を終了します。

これでルートを逆から読めばAからGまでのルートがわかります。

今回出てこなかったEへのルートも算出してみます。

Eをルートに追加します。Eの親はCなのでCを参照します。

Cをルートに追加します。Cの親はAなのでAを参照します。

Aをルートに追加します。

ルートを逆に読むことでAからEまでのルートがわかります。

以上ルートの算出でした。

続きます。