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

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

<関数名>
  apsp — 全ての頂点に対する最短経路問題

<形式>
  void apsp(int *shortest, int *distance, int numOfCity);

<引数>
  shortest  (出力)最短距離が入っている配列
  distance  (入力)市と市との直接距離
  numOfCity (入力)市の数

<関数値>
  なし

<注意事項>
  引数 shortest、distance は numOfCity X numOfCity の2次元配列のつもりで利用すること。市に番号 1 ~ n を割りふったとき、
   distance[0]         市1から市1まで(自分自身へ)の距離
   distance[1]         市1から市2までの距離
   distance[numOfCity-1] 市1から市nまでの距離
   distance[numOfCity]   市2から市1までの距離
   distance[numOfCity+1] 市2から市2(自分自身へ)の距離

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

<用例>
  C言語プログラム(apsp-test.c
  使い方ですが、まずデータファイルを用意しておく。市の数をデータファイルの1行目に書く。2行目からは1行ごとに各市間の距離を書く。2市間の直接経路がないときは、無限大のつもりで大きな数字(たとえば 20000)を使う。

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

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

<C言語関数>
  (apsp.c

<説明>
  本プログラムには Floyd のアルゴリズムを使っている。実行時間は市の数の3乗オーダ。

Comments are closed.

Post Navigation