apsp

最短経路問題

関数名

apsp　全ての頂点に対する最短経路問題（All-Pairs Shortest Paths Problem、APSP問題）。つまり、いくつかの市があり、市と市との間の距離が分かったとき、ある市から他の市までの最短距離を求める問題である。

形式

void apsp(int *shortest, int *distance, int numOfCity);

引数

shortest   （出力）最短距離が入っている配列
distance   （入力）市と市との直接距離
numOfCity  （入力）市の数

関数値

なし

注意事項

引数 shortest、distance は numOfCity X numOfCity の２次元配列のつもりでご利用ください。市に番号 1 ～ n を割りふったとき、

    distance[0]            市１から市１まで（自分自身へ）の距離
    distance[1]            市１から市２までの距離
    distance[numOfCity-1]  市１から市nまでの距離
    distance[numOfCity]    市２から市１までの距離
    distance[numOfCity+1]  市２から市２（自分自身へ）の距離

となる。つまり、numOfCity分の配列要素ごとに、ある市から他のすべての市への距離がdistance配列に入っている。
なお、自分自身への距離は常に0であり、市間の直接経路がないときは、無限大のつもりで大きい値を使うとよい。

用例

用例プログラム（apsp-test.c）

使い方ですが、まずデータファイルを用意しておく。市の数をデータファイルの1行目に書く。2行目からは1行ごとに各市間の距離を書く。２市間の直接経路がないときは、無限大のつもりで大きな数字（たとえば 20000)を使う。

    3        <-- 市の数
    0        <-- 市１から市１（自分自身）への距離
    20       <-- 市１から市２への距離
    20000    <-- 市１から市３への距離（直接経路がないので、無限大）
    20       <-- 市２から市１への距離
    0        <-- 市２から市２（自分自身）への距離
    10       <-- 市２から市３への距離
    25       <-- 市３から市１への距離（片通行の道はある）
    10       <-- 市３から市２への距離
    0        <-- 市３から市３（自分自身）への距離

でデータファイルを書く。つぎに、用例プログラムは
　　　apsp-test　データファイル
で実行すれば、各市間の最短距離が表示される。

プログラム（apsp.c）

void apsp(int *shortest, int *distance, int numOfCity){
    int  i, j, k;
    int  *s, *d;
    int  x;
    
    s = shortest;
    d = distance;
    for (i = 0; i < numOfCity; i++)
        for (j = 0; j < numOfCity; j++) {
            *s++ = (j != i) ? *d : 0;
            d++;
        }

    for (k = 0; k < numOfCity; k++) {
        s = shortest;
        for (i = 0; i < numOfCity; i++)
            for (j = 0; j < numOfCity; j++) {
                if (*s > (x = *(shortest + i*numOfCity + k) 
                            + *(shortest + k*numOfCity + j)))
                    *s = x;
                s++;
            }
    }
}

説明

本プログラムには Floyd の方法を使っている。実行時間は市数の 3 乗オーダである。

市の代わりに駅を考え、距離の代わりに電車代を考えると、この問題は駅から駅までの最低乗り換え電車運賃を求める問題となる。したがって、応用範囲は実に広い。最近のカーナビもその一例であろう。

関連関数