ちょうどk本の辺で到達する最短経路を求めるアルゴリズム

重み付き有向グラフが与えられ、各頂点間の辺の重みがコスト行列として表されているとします。さらに、始点となる頂点 u と終点となる頂点 v、そして使用する辺の本数 k も与えられます。この課題は、ちょうど k 本の辺を使って頂点 u から頂点 v へ移動するときの最短距離を求めることです。

問題のアプローチ

この問題を解くには、始点 u から出発し、隣接するすべての頂点へ順に移動していきます。その際、再帰呼び出しのたびに残りの辺数 k を 1 ずつ減らしながら探索を進めることで、正確に k 本の辺を使う経路の中から最小のコストを見つけ出します。

入力と出力

Input:
グラフのコスト行列
0 10 3 2
∞  0 ∞ 7
∞  ∞ 0 6
∞  ∞ ∞ 0

Output:
Weight of the shortest path is 9

上記の例では、頂点0から頂点3まで、ちょうど2本の辺（0 → 2 → 3）を使った経路のコストは 3 + 6 = 9 となり、これが最短となります。

アルゴリズム

shortKEdgePath(u, v, edge)

入力 − 頂点 u と v、および辺の本数 edge。

出力 − 最短経路の距離。

Begin
    if edge = 0 and u = v, then
        return 0
    if edge = 1 and cost[u, v] ≠ ∞, then
        return cost[u, v]
    if edge <= 0, then
        return ∞
    set shortPath := ∞

    for all vertices i, do
        if cost[u, i] ≠ ∞ and u ≠ i and v ≠ i, then
            tempRes := shortKEdgePath(i, v, edge - 1)
            if tempRes ≠ ∞, then
                shortPath = minimum of shortPath and (cost[u,i]+tempRes)
    done
    return shortPath
End

アルゴリズムのポイント

• edge = 0 かつ u = v の場合： 移動不要なのでコストは 0 を返します。
• edge = 1 かつ cost[u][v] ≠ ∞ の場合： 直接つながる辺が存在するので、そのコストをそのまま返します。
• edge ≤ 0 の場合： 有効な経路が存在しないため、無限大（∞）を返します。

C++による実装例

#include <iostream>
#define NODE 4
#define INF INT_MAX
using namespace std;

int cost[NODE][NODE] = {
    {0, 10, 3, 2},
    {INF, 0, INF, 7},
    {INF, INF, 0, 6},
    {INF, INF, INF, 0}
};

int minimum(int a, int b) {
    return (a<b)?a:b;
}

int shortKEdgePath(int u, int v, int edge) {
    // 辺数が0で始点と終点が同じなら、経路なしとして0を返す
    if (edge == 0 && u == v)
        return 0;
    // 辺数が1で(u,v)間に直接の辺がある場合はそのコストを返す
    if (edge == 1 && cost[u][v] != INF)
        return cost[u][v];
    // 辺数が負になった場合は解なしとして無限大を返す
    if (edge <= 0)
        return INF;
    int shortPath = INF;

    // uに隣接するすべての頂点iについて再帰的に探索
    for (int i = 0; i < NODE; i++) {
        if (cost[u][i] != INF && u != i && v != i) {
            int tempRes = shortKEdgePath(i, v, edge-1);
            if (tempRes != INF)
                shortPath = minimum(shortPath, cost[u][i] + tempRes);
        }
    }
    return shortPath;
}

int main() {
    int src = 0, dest = 3, k = 2;
    cout << "Weight of the shortest path is " << shortKEdgePath(src, dest, k);
}

実行結果

Weight of the shortest path is 9

計算量について

この再帰的なアプローチでは、各ステップですべての隣接頂点を試すため、時間計算量は O(V^k) となり、k が大きくなると指数的に増加します。動的計画法（メモ化）を組み合わせることで、状態 (u, v, edge) の組み合わせをキャッシュし、計算量を O(k・V^2) 程度に抑えることが可能です。また、グラフの辺の重みがすべて非負である場合には、DPテーブルを用いた反復的な解法も有効です。