トイレに座ってアルゴリズムを読む: わずか5行のフロイドの最短経路アルゴリズム

[[110550]]

夏休みの間、シャオ・ヘンはいくつかの都市を旅行する予定です。下の図に示すように、都市間に道路がある都市もあれば、ない都市もあります。お金を節約し、旅行の計画を容易にするために、シャオ・ヘンさんは出発前に2つの都市間の最短距離を知りたいと考えています。

上の写真では、4 つの都市に 8 本の道路があります。道路上の数字は道路の長さを示しています。これらの道路は一方通行ですので、ご注意ください。ここで、任意の 2 つの都市間の最短距離、つまり任意の 2 つの地点間の最短経路を見つける必要があります。この問題は、「マルチソース最短経路」問題としても知られています。

ここで、グラフ情報を格納するためのデータ構造が必要です。これを格納するために、4*4 行列 (2 次元配列 e) を使用することもできます。たとえば、都市 1 から都市 2 までの距離が 2 の場合、e[1][2] の値を 2 に設定します。都市 2 が都市 4 に到達できない場合は、e[2][4] の値を∞に設定します。さらに、都市からその都市自体までの距離も0であることがここで合意されており、たとえば、次のようにe[1][1]は0です。

さて、質問に戻ります。任意の 2 点間の最短経路を見つけるにはどうすればよいでしょうか?これまでの研究から、2 点間の最短経路は深さ優先探索または幅優先探索によって見つけられることがわかっています。したがって、n2 の深さ優先探索または幅優先探索を実行することによって、つまり、2 つのポイントごとに深さ優先探索または幅優先探索を実行することによって、任意の 2 つのポイント間の最短経路を取得できます。しかし、他に方法はあるのでしょうか?

考えてみましょう。これまでの経験によれば、任意の 2 点間の距離 (たとえば、頂点 a から頂点 b まで) を短縮したい場合、頂点 a から頂点 b までの元の距離を短縮するには、3 番目の点 (頂点 k) を導入し、この頂点 k を介して転送する (つまり、a->k->b) しかありません。では、1～n のうちどの点が通過頂点 k になるのでしょうか?場合によっては、1 つのポイントではなく、2 つ以上のポイントを経由して転送する方がさらに短くなることがあります。つまり、a->k1->k2b-> または a->k1->k2…->k->i…->b です。たとえば、上の図では、都市4から都市3までの距離e[4][3] (4->3)は元々12でした。都市1のみを乗り換える場合（4->1->3）、移動時間は11に短縮されます（e[4][1]+e[1][3]=5+6=11）。実際、都市1から都市3への移動は都市2を経由して行うこともできるため、都市1から都市3までの距離は5に短縮されます（e[1][2]+e[2][3]=2+3=5）。したがって、都市 1 と都市 2 を同時に乗り換えると、都市 4 から都市 3 までの距離はさらに 10 に短縮されます。この例から、各頂点には他の 2 つの頂点間の距離を短縮する可能性があることがわかります。さて、この問題を一般化してみましょう。

任意の 2 つの点が 3 番目の点を通過できない場合、これらの都市間の最短距離は次の初期距離になります。

頂点 1 のみを通過できる場合、任意の 2 点間の最短距離をどのように見つければよいでしょうか? e[i][1]+e[1][j]がe[i][j]より小さいかどうかを判断するだけです。 e[i][j]は頂点iから頂点jまでの距離を表します。 e[i][1]+e[1][j]は、頂点iから頂点1までの距離の合計と、頂点1から頂点jまでの距離の合計を表します。このうち、i は 1~n ループ、j も 1~n ループであり、コード実装は次のようになります。

 (i= 1 ;i<=n;i++)の場合
{ 
     (j= 1 ;j<=n;j++)の場合
    { 
 もしe[i][j] > e[i][ 1 ]+e[ 1 ][j]ならば
e[i][j] = e[i][ 1 ]+e[ 1 ][j];
    }
 }

頂点 1 のみが通過できる場合、任意の 2 点間の最短距離は次のように更新されます。

上の図から、頂点1のみを通過する場合、頂点3から頂点2 (e[3][2])、頂点4から頂点2 (e[4][2])、頂点4から頂点3 (e[4][3]) までの距離がすべて短縮されることがわかります。

次に、頂点 1 と 2 のみを通過しながら、任意の 2 点間の最短距離を探し続けます。どうやってやるんですか？頂点 1 のみを通過した場合の任意の 2 点間の最短距離の結果に基づいて、頂点 i と頂点 j の間の距離が頂点 2 を通過することによって短縮できるかどうかを判断する必要があります。つまり、e[i][2]+e[2][j]がe[i][j]より小さいかどうかを判断します。コードは次のように実装されています。

 // 頂点1を通過 
 (i= 1 ;i<=n;i++)の場合
     (j= 1 ;j<=n;j++)の場合
  e[i][j] > e[i][ 1 ]+e[ 1 ][j]の場合、e[i][j]=e[i][ 1 ]+e[ 1 ][j];
 // 頂点2を通過 
 (i= 1 ;i<=n;i++)の場合
     (j= 1 ;j<=n;j++)の場合
  e[i][j] > e[i][ 2 ]+e[ 2 ][j]の場合、e[i][j]=e[i][ 2 ]+e[ 2 ][j] となります。

頂点 1 と 2 のみが通過できる場合、任意の 2 点間の最短距離は次のように更新されます。

上図から、頂点1のみを経由した転送が許可されている場合と比較して、ここでは頂点1と2を経由した転送が許可されているため、e[1][3]とe[4][3]の距離が短くなることがわかります。

同様に、頂点 1、2、3 のみを経由する転送を許可しながら、任意の 2 点間の最短距離を探し続けます。任意の 2 点間の最短距離は次のように更新されます。

***すべての頂点を通過点として使用できるようにすると、任意の 2 点間の最終的な最短距離は次のようになります。

アルゴリズムのプロセス全体を説明するのは複雑ですが、コードの実装は非常にシンプルで、コアコードはわずか 5 行です。

 (k= 1 ;k<=n;k++)の場合
     (i= 1 ;i<=n;i++)の場合
  (j= 1 ;j<=n;j++)の場合
     もし(e[i][j]>e[i][k]+e[k][j])
   e[i][j]=e[i][k]+e[k][j];

このコードの基本的な考え方は、最初は頂点 1 を通る通過のみが許可され、次に頂点 1 と 2 を通る通過のみが許可され、頂点 1 から n までのすべての通過が許可され、任意の 2 点間の最短距離が見つかるというものです。一言でまとめると、頂点 i から頂点 j までの最短距離は、最初の k 点を通る距離です。実際、これは一種の「動的プログラミング」の考え方であり、これについては「Aha!アルゴリズム 2: 偉大な心が輝くときについて詳しく説明します。このアルゴリズムの完全なコードは次のとおりです。

 #include <stdio.h>
 intメイン()
 { 
     int e[ 10 ][ 10 ],k,​​i,j,n,m,t1,t2,t3; 
     int inf= 99999999 ; // inf（無限大の略）を使用して、考えられる正の無限大の値を保存します。  
     //n と m を読み込み、n は頂点の数、m は辺の数を表します 
    scanf( "%d %d" ,&n,&m); 
  
     //初期化 
     (i= 1 ;i<=n;i++)の場合
  (j= 1 ;j<=n;j++)の場合
      i==j の場合、e[i][j] = 0 ;
それ以外の場合はe[i][j]=inf; 
     //エッジを読み込む 
     (i= 1 ;i<=m;i++)の場合
    {
 scanf( "%d %d %d" ,&t1,&t2,&t3);
 t1 = t2 = t3;
    } 
  
     //フロイド・ワーシャルアルゴリズムのコアステートメント 
     (k= 1 ;k<=n;k++)の場合
  (i= 1 ;i<=n;i++)の場合
      (j= 1 ;j<=n;j++)の場合
  もし(e[i][j]>e[i][k]+e[k][j] )
      e[i][j]=e[i][k]+e[k][j]; 
  
     // 最終結果を出力する 
     (i= 1 ;i<=n;i++)の場合
    { 
      (j= 1 ;j<=n;j++)の場合
 {
     printf( "%10d" 、e[i][j]);
 }
 printf( "\n" );
    } 
  
    戻る  0 ;
 }

注意すべき点の 1 つは、正の無限大をどのように表現するかです。通常、正の無限大は 99999999 と定義されます。これは、2 つの正の無限大を加算しても、その合計が int 型の範囲を超えないためです (C 言語の int 型に格納できる最大の正の整数は 2147483647 です)。実際のアプリケーションでは、最短経路の上限を推定し、それよりも少しだけ大きく設定するのが最適です。たとえば、エッジが 100 個あり、各エッジが 100 を超えない場合は、正の無限大を 10001 に設定するだけです。正の無限大を他の値に追加して正の無限大より大きい数値を取得することは許可されていないと思われる場合は、比較するときに 2 つの判断条件を追加するだけで済みます。次のコードの下線付きの記述に注意してください。

 //フロイド・ワーシャルアルゴリズムのコアステートメント 
 (k= 1 ;k<=n;k++)の場合
   (i= 1 ;i<=n;i++)の場合
       (j= 1 ;j<=n;j++)の場合
 もし(e[i][k]<inf && e[k][j]<inf && e[i][j]>e[i][k]+e[k][j])
     e[i][j]=e[i][k]+e[k][j];

上記コードの入力データスタイルは次のとおりです。

 4   8    
 1   2   2    
 1   3   6    
 1   4   4    
 2   3   3    
 3   1   7    
 3   4   1    
 4   1   5    
 4   3   12  

行の最初の 2 つの数字は n と m です。ここで、n は頂点の数を表し、m は辺の数を表します。

次の m 行にはそれぞれ 3 つの数値 t1、t2、t3 が含まれており、頂点 t1 から頂点 t2 までの距離が t3 であることを示しています。

最終結果は次のとおりです。

このようにして、任意の 2 点間の最短経路を見つけることができます。時間計算量はO(N3)です。非常に印象的なのは、必要なコードが 5 行だけで、実装が非常に簡単なことです。実装が非常に簡単なため、時間の複雑さの要件が高くない場合は、Floyd-Warshall を使用して、指定された 2 つのポイント間の最短経路、または指定されたポイントから残りの頂点までの最短経路を見つけることも可能です。もちろん、より高速なアルゴリズムもあります。次のセクション「ダイクストラ アルゴリズム」を参照してください。

もう一つ注意すべき点は、Floyd-Warshall アルゴリズムは「負の重みのループ」 (または「負の重みのリング」) を持つグラフを解くことができないということです。これは、「負の重みのループ」を持つグラフには最短経路がないためです。たとえば、以下のグラフでは、頂点 1 から頂点 3 への最短経路は存在しません。なぜなら、1->2->3->1->2->3->…->1->2->3 のようなパスでは、1->-2>3 のようなループを回るたびに、最短パスが 1 ずつ減少し、最短パスが見つかることは決してないからです。実際、グラフに「負の重みループ」がある場合、そのグラフには最短パスがありません。

このアルゴリズムは、1962 年に Robert W. Floyd によって「Communications of the ACM」で公開されました。同年、スティーブン・ウォーシャルも独自にこのアルゴリズムを発表しました。ロバート W.フロイドは稀有な才能の持ち主でした。もともとシカゴ大学で文学を学んでいましたが、当時の米国経済があまり良くなかったため、仕事を見つけるのは困難でした。仕方なくウェスティングハウス・エレクトリック・カンパニーのコンピューター・オペレーターとして働き、IBM 650 コンピューター室で夜勤をしながら、コンピューターのキャリアをスタートさせました。さらに、彼と JWJ Williams は 1964 年に有名なヒープ ソート アルゴリズム HEAPSORT を共同発明しました。ヒープソートアルゴリズムについては第 7 章で学習します。ロバート W.フロイドは1987年にチューリング賞を受賞した。

ブログアドレス: http://ahalei.blog..com/4767671/1383613