電車で目的地に到達するための最小費用を求めるアルゴリズム(動的計画法)

ある旅路には N 個の停車駅があり、乗り物は駅 0 から出発して駅 N-1 まで進みます。すべての駅同士のペアに対する切符代(運賃)が表として与えられているとき、それらの運賃の中から組み合わせて、目的地に到達するための最小費用を求めます。

たとえば、途中の駅を経由したほうが直行よりも安くなる場合があります。与えられた運賃表をもとに、最も安い移動経路を見つけるのがこの問題の目的です。

入力と出力

入力:
旅程のコスト行列
0  15  80  90
∞   0  40  50
∞   ∞   0  70
∞   ∞   ∞   0

出力:
最小費用は 65。
最初に駅 0 から駅 1 へ移動し(費用 15)、次に駅 1 から駅 3 へ移動します(費用 50)。合計費用は 65 になります。

この例では、駅 0 から駅 3 へ直行すると費用 90 かかりますが、駅 1 を経由する経路(15 + 50 = 65)のほうが安く済みます。他の候補としては「駅 2 経由」(80 + 70 = 150)や「駅 1・駅 2 の両方を経由」(15 + 40 + 70 = 125)がありますが、いずれも 65 を下回らないため、65 が最小費用となります。

アルゴリズム

findMinCost(cost)

入力 − 各始点から各目的地への運賃を格納したコスト行列。

出力 − 目的地に到達するための最小費用。

Begin
    define array costLoc, whose size is same as number of locations,
    fill costLoc with ∞.
    n := number of locations
    costLoc[0] := 0

    for each source i to each destination j, do
        if costLoc[j] > costLoc[i] + cost[i, j], then
            costLoc[j] := costLoc[i] + cost[i, j]
    done

    return costLoc[n-1]
End

このアルゴリズムは動的計画法(DP)の一種です。「駅 0 から各駅 j に到達するまでの最小費用」を配列 costLoc に順番に記録していきます。駅 i から駅 j へ直接移動する費用(costLoc[i] + cost[i][j])が、すでに記録されている costLoc[j] より安ければ、その値で更新します。

すべての駅の組み合わせを確認し終えた時点で、costLoc[n-1] に最終駅への最小費用が残ります。計算量は二重ループにより O(N²) です。

C++ による実装例

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

int cost[NODE][NODE] = {
    {0, 15, 80, 90},
    {INF, 0, 40, 50},
    {INF, INF, 0, 70},
    {INF, INF, INF, 0}
};

int findMinCost() {            // 目的地に到達するための最小費用を求める
    int costStation[NODE];     // 駅 0 から各駅への到達費用を格納

    for (int i = 0; i < NODE; i++)
        costStation[i] = INF;  // 初期値はすべて無限大
    costStation[0] = 0;        // 出発地である駅 0 の費用は 0

    for (int i = 0; i < NODE; i++)
        for (int j = i + 1; j < NODE; j++)
            if (costStation[j] > costStation[i] + cost[i][j])  // より安い経路があれば更新
                costStation[j] = costStation[i] + cost[i][j];

    return costStation[NODE - 1];
}

int main() {
    cout << "The minimum cost to reach destination is " << findMinCost() << endl;
    return 0;
}

ポイント: INT_MAX(無限大の代わり)を使用するため、<climits> ヘッダーのインクルードが必要です。また、運賃行列では後ろの駅から前の駅へ戻る移動ができない(値が INF)ため、内側のループは j = i + 1 から始めても問題ありません。

出力

The minimum cost to reach destination is 65

まとめ

この問題は、区間ごとの運賃がすべて既知である場合に、複数の乗り換えパターンの中から総額が最も安くなる経路を選ぶ典型的な最短路問題です。DP 配列を左から右へ更新していくだけで答えが得られるため、実装もシンプルで、計算量 O(N²) と実用的な速度で動作します。