ちょうどk本の辺で始点から終点へ至るウォークの総数を動的計画法で求める方法

問題の概要

有向グラフが1つ与えられ、あわせて2つの頂点 u(始点)と v(終点)が指定されます。この課題では、ちょうど k 本の辺を使って頂点 u から v に到達する「ウォーク(歩行経路)」の総数を求めます。辺の本数 k の値もアルゴリズムへの入力として与えられます。

この問題は動的計画法(DP)で効率よく解くことができます。まず、n × n × (k+1) のサイズを持つ3次元テーブルを作成します。行には始点側の頂点番号 i、列には終点側の頂点番号 j を対応させ、奥行き(第3の次元)は始点から目的地までに使用した辺の本数を記録するために使います。

漸化式としては、「i から j へ e 本の辺で到達する経路数 = i の各隣接頂点 a について『a から j へ e−1 本の辺で到達する経路数』の総和」と定義できます。これにより、小さな部分問題から順に答えを積み上げていくことができます。

入力と出力

入力:
グラフの隣接行列(終点は頂点 3、K = 2)
0 1 1 1
0 0 0 1
0 0 0 1
0 0 0 0

出力:
頂点 0 から頂点 3 へ、2 本の辺で到達できるウォークは 2 通りある

アルゴリズム

入力: 始点 u、終点 v、辺の本数 k。

出力: k 本の辺で構成できるウォークの総数。

Begin
    // n は頂点の総数。(n × n × (k+1)) の3次元配列 count を宣言
    for edge = 0 to k do
        for i = 0 to n-1 do
            for j = 0 to n-1 do
                count[i][j][edge] := 0
                if edge = 0 and i = j then
                    count[i][j][edge] := 1     // 辺0本で i と j が同一なら 1 通り
                if edge = 1 and (i, j) 間に辺が存在 then
                    count[i][j][edge] := 1     // 直接の辺があれば 1 通り
                if edge > 1 then
                    for a = 0 to n-1 and a が i に隣接 do
                        count[i][j][edge] := count[i][j][edge] + count[a][j][edge - 1]
                    done
            done
        done
    done
    return count[u][v][k]
End

C++による実装例

#include <iostream>
#define NODE 4   // グラフの頂点数
using namespace std;

int graph[NODE][NODE] = {
    {0, 1, 1, 1},
    {0, 0, 0, 1},
    {0, 0, 0, 1},
    {0, 0, 0, 0}
};

int numberOfWalks(int u, int v, int k) {
    int count[NODE][NODE][k+1];

    for (int edge = 0; edge <= k; edge++) {           // 辺の本数 0〜k について
        for (int i = 0; i < NODE; i++) {
            for (int j = 0; j < NODE; j++) {
                count[i][j][edge] = 0;                // まずすべて 0 で初期化

                if (edge == 0 && i == j)              // 辺0本で i と j が同じ頂点なら 1 通り
                    count[i][j][edge] = 1;
                if (edge == 1 && graph[i][j])         // 辺1本で i から j へ直結していれば 1 通り
                    count[i][j][edge] = 1;
                if (edge > 1) {                       // 辺が2本以上の場合
                    for (int a = 0; a < NODE; a++)    // 始点 i の隣接頂点を走査
                        if (graph[i][a])
                            count[i][j][edge] += count[a][j][edge-1];
                }
            }
        }
    }
    return count[u][v][k];
}

int main() {
    int u = 0, v = 3, k = 2;
    cout << "頂点 " << u << " から " << v << " へ、"
         << k << " 本の辺で到達できるウォークは "
         << numberOfWalks(u, v, k) << " 通りです。";
}

出力結果

頂点 0 から 3 へ、2 本の辺で到達できるウォークは 2 通りです。

計算量

頂点数を n、指定された辺の本数を k とすると、3重ループの内部でさらに隣接頂点を走査するため、時間計算量は O(k·n³) となります。また、3次元テーブルを保持する必要があるため、空間計算量は O(k·n²) です。同じ部分問題を繰り返し計算しない動的計画法のアプローチにより、単純な全探索よりも大幅に効率的に答えを求められます。