動的計画法(DP)で最短距離を求める(C++)

最短経路問題について

以下の0~6のノードがある経路があります。矢印と数値はノード間の距離を示します(例：ノード0と1の距離は4)。
0から6までの最短距離と求めるといくつになるでしょう?

真っ先に思いつく方法は全経路の距離を求めて、その距離を求めればよいです。この図の場合、

• 0 ⇒ 1 ⇒ 4 ⇒ 6
• 0 ⇒ 1 ⇒ 2 ⇒ 5 ⇒ 6
• 0 ⇒ 1 ⇒ 2 ⇒ 3 ⇒ 5 ⇒ 6
• 0 ⇒ 3 ⇒ 5 ⇒ 6

の4通りが存在するので、これでも求められます。
しかし、ノードが増えるほどこの数え上げは大変になり、効率が良いとは言えません。
そこで今回注目するのが動的計画法です。

動的計画法の導入

以下の解説では、ノード0~iまでの最短距離をとします。
仮にとが分かれば以下の図のように、ノード6までの最短距離は容易に求められます。

そして、はとが分かれば同様に求められます。

同様に、~が求められればが求まることはわかると思います。
このように、経路全体を分割して部分ごとに考える手法が動的計画法というイメージで大丈夫です。

動的計画法による最短距離の求め方

ここから動的計画法の具体的なアルゴリズムを紹介します。
先ほどまでの説明ではゴールから順に逆算しましたが、プログラム的にはスタートから考える方が楽です。そのため、ノード0との隣接、ノード1との隣接、…という風に計算していきます。
また、を保存しておく表を用意します。ノード0⇒0は移動がないので=０です。

i	0	1	2	3	4	5	6
	0	?	?	?	?	?	?

ノード0

隣接するノード：1、3
もにはまだ数値が格納されていないので、ノード0からの距離を格納します。

i	0	1	2	3	4	5	6
	0	4	?	5	?	?	?

ノード1

隣接するノード：2、4
もにはまだ数値が格納されていないので、ノード0⇒1の距離()＋ノード1⇒各ノードまでの距離、つまり、

• 
• 

を格納します。

i	0	1	2	3	4	5	6
	0	4	5	5	9	?	?

ノード2

隣接するノード：3、5
にはまだ数値がないので、

を格納。
一方、には既に0⇒3の距離が格納されています。この場合は、

• 現在のの値
• ノード2を経由した、0⇒1⇒2⇒3の距離

の最小値を取ることにします。これは2値の最小値を求める関数minを使って、

と表せます(値はそのまま)。

i	0	1	2	3	4	5	6
	0	4	5	5	9	7	?

最終結果

このように計算することで、全を求められます(下記アニメーション参考)

最終的に表は以下のようになるので、が求まる。

i	0	1	2	3	4	5	6
	0	4	5	5	9	7	8

参考：ノード3以降の詳細な計算

ノード3

隣接するノード：5

i	0	1	2	3	4	5	6
	0	4	5	5	9	7	?

ノード4

隣接するノード：6

i	0	1	2	3	4	5	6
	0	4	5	5	9	7	14

ノード5

隣接するノード：6

i	0	1	2	3	4	5	6
	0	4	5	5	9	7	8

プログラム実装上の注意

• 基本的には先ほどのアルゴリズムをしっかりと実装すればOKですが、どのノード同士が接続されているかをしっかりプログラムに落とす必要があります。
• 基本的には、二次元配列を使うことが望ましく、縦に示した数字が始点で横に示した数字を終点とすることが望ましいです。数値が0の場合は繋がっていないとします。
• 例)表の赤文字は3⇒5の距離が3であることを示す。
• また、を格納する配列は十分に大きな値や-1などの値で初期化して、うまく条件分岐しましょう。

	0	1	2	3	4	5	6
0	0	4	0	5	0	0	0
1	0	0	1	0	5	0	0
2	0	0	0	3	0	2	0
3	0	0	0	0	0	3	0
4	0	0	0	0	0	0	5
5	0	0	0	0	0	0	1

C++での実装例

ソースコード

#include <iostream>
using namespace std;

#define N 7

int main() {

    // マップ
    int map[N - 1][N] = {
        {0, 4, 0, 5, 0, 0, 0},
        {0, 0, 1, 0, 5, 0, 0},
        {0, 0, 0, 3, 0, 2, 0},
        {0, 0, 0, 0, 0, 3, 0},
        {0, 0, 0, 0, 0, 0, 5},
        {0, 0, 0, 0, 0, 0, 1},
    };

    // DP法のテーブル
    int dp[N] = { 0, 999, 999, 999, 999, 999, 999 };

    // 計算
    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < N; j++) {
            int x = map[i][j];
            if (x > 0) {
                int y = x + dp[i];

                if (y < dp[j]) {
                    dp[j] = y;
                }
            }
        }
    }

    // テーブルの表示
    cout << "dp = { ";
    for (int i = 0; i < N; i++) {
        cout << dp[i] << ", ";
    }
    cout << "}" << endl;

    // 最短距離の表示
    cout << "d_6 = " << dp[N - 1] << endl;
}

実行結果

dp = { 0, 4, 5, 5, 9, 7, 8, }
d_6 = 8