[]
夏休みの間、ハムさんはいくつかの都市を旅行する予定です。下の図のように、都市と都市の間に道路があるところとないところがあります。お金を節約し、旅行の計画を立てやすくするため、リトルハムは出発時に2つの都市間の最短距離を知りたいと考えています。
上の地図は4つの都市にある8つの道路を示しており、道路上の数字はこの道路の長さを示しています。これらの道路は一方通行であることに注意してください．ここで，任意の2都市間の最短距離，つまり任意の2点間の最短経路を求める必要があります．この問題は「マルチソース最短経路」問題としても知られています．
ここで，グラフの情報を格納するためのデータ構造が必要になりますが，これはやはり4*4の行列に格納することができます．例えば，都市1から都市2までの距離が2であれば，e[1][2]の値を2とし，都市2が都市4に到達できなければ，e[2][4]の値を∞とします．また，ここでは，e[1][1]が0であるように，自分自身にある都市も0であることに同意します．
では、2点間の最短経路を求めるにはどうすればよいのでしょうか？2点間の最短経路は、深さ優先探索または幅優先探索によって見つけられることが分かっています。つまり、深さ優先探索または幅優先探索をn2回、つまり2点ごとに1回行えば、任意の2点間の最短経路を求めることができます。しかし、他に方法はないのでしょうか？
そういえば、これまでの経験では、任意の2点間の距離を縮めたい場合、頂点aから頂点bへの本来の距離を縮めるには、第3の点を導入し、この頂点kを経由させる、つまりa->k->bのようにすればよいのでした。では、この経由点kは1からnまでのどの点でしょうか？a->k1->k2b->あるいはa->k1->k2...->k->i...->bのように，1つの点だけでなく2つ以上の点を経由した方が短い場合もあります．上図の都市4から都市3までの距離e[4][3]は本来12であり，都市1だけを経由すれば距離は11に短縮されます． 実は都市1から都市3は都市2も経由することができ，都市1から都市3までの距離は5に短縮されるので，都市1と都市2を同時に経由すれば，都市4から都市3までの距離はさらに短縮され10になります． この例から，各頂点は頂点でない限り都市4から都市3までの距離を作ることができることがわかりました．つまり，各頂点は他の2つの頂点間の距離を縮める可能性があるということです．では，この問題の一般化です．
どの2点間にも第3点が通らない場合、これらの都市間の最短距離は次のように初期距離となります。
頂点1を通過することしか許されなくなった場合、どのように任意の2点間の最短距離を求めればよいのでしょうか。e[i][j]は頂点iから頂点jまでの距離を表し、e[i][1]+e[1][j]は頂点iから頂点1までの距離と頂点1から頂点jまでの距離の和を表します。iが1からnのサイクル、jも1からnのサイクルである場合、コードは次のように実装されます。
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if ( e[i][j] > e[i][1]+e[1][j] )
e[i][j] = e[i][1]+e[1][j];
}
}
任意の2点間を移動する最短距離は、頂点1だけが通過できるように更新されます：
上の図から、頂点3から頂点2、頂点4から頂点2、頂点4から頂点3への移動は、頂点1のみを経由する場合に短くなることがわかります。
次に、2つの頂点（1と2）だけが通過できる場合の、任意の2点間の最短距離を求めます。どうやるの？頂点#1だけを通過させたときの任意の2点間の最短距離を求め、頂点#2を通過させることで頂点#iと頂点#jの間の距離が短くなるかどうかを判断します。つまり、e[i][2] + e[2][j]がe[i][j]より小さいかどうかを判定するために、コードは次のように実装されます。
//第1頂点の後
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (e[i][j] > e[i][1]+e[1][j]) e[i][j]=e[i][1]+e[1][j];
//2頂点の後
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (e[i][j] > e[i][2]+e[2][j]) e[i][j]=e[i][2]+e[2][j];
任意の2点間を移動する最短距離は、頂点1と頂点2だけが通過できるように更新されます：
上の図から、頂点1のみの通過を許可するのに比べ、ここでは頂点1と2の通過が許可されているため、e[1][3]とe[4][3]の旅程が短くなっていることがわかります。
同様に、頂点1,2,3の通過のみを許しながら、任意の2点間の最短移動距離を求め続けます。任意の2点間の最短移動距離は次のように更新されます：
*** すべての頂点を通過することを許すと、2点間の最終的な最短距離は次のようになります：
アルゴリズミックなプロセス全体は、控えめに言っても面倒ですが、コードでの実装は非常にシンプルで、コアコードはわずか5行です：
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
このコードの基本的な考え方は、任意の2点間の最短距離を、最初に頂点1を通過することだけを許し、次に頂点1と2を通過することだけを許し......すべての頂点1〜nを通過することを許すことによって求めることです。一言で言えば、頂点iから頂点jまで、最短距離の最初のk点だけを通るということです。これは実は「動的計画法」のアイデアで、嗚呼で説明します！Algorithm 2 - When Great Minds Shine」で説明します。このアルゴリズムの完全なコードを以下に示します：
#include <stdio.h>
int main()
{
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);
//初期化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j) e[i][j]=0;
else e[i][j]=inf;
//サイドを読む
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
//Floyd-Warshallアルゴリズム・コア・ステートメント
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j] )
e[i][j]=e[i][k]+e[k][j];
//最終結果を出力する
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%10d",e[i][j]);
}
printf("
");
}
return 0;
}
注意すべき点は、正の無限大の表現方法です。正の無限大は通常999999999と定義されます。なぜなら、2つの正の無限大を足し合わせても、その合計はint型の範囲を超えないからです。実際には *** 最短経路の上限を見積もるには、それを少し大きく設定するだけです。例えば、100 個の辺があり、それぞれの辺が 100 を超えない場合、正の無限大を 10001 に設定すればよいのです。もし、正の無限大と他の値を足して、正の無限大より大きな数を求めることが許されないとお考えの場合は、比較に2つの判定条件を追加すればよいので、下線部の記述に以下のコードを注意してください。
//Floyd-Warshallアルゴリズム・コア・ステートメント
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(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
*** nは頂点の数、mは辺の数を表します。
次のm行は、それぞれ3つの数字t1、t2、t3で、頂点t1から頂点t2までの距離がt3であることを示しています。
最終的な結果は以下の通り：
また、「負の重みループ」を持つグラフは最短経路を持たないので、フロイド・ウォーシャル・アルゴリズムは「負の重みループ」を持つグラフを解くことができないことに注意してください。例えば、次のグラフは頂点1から頂点3への最短経路を持ちません。なぜなら、1->2->3->1->2->3->...->1->2->3の経路では、ループ1->2->3を回るたびに最短経路が1ずつ減っていき、最短経路を見つけることができないからです。実際、グラフに「負の重みのループ」がある場合、そのグラフには最短路がありません。
このアルゴリズムは、1962年にロバート・W・フロイドが「コミュニケーションズ・オブ・ザ・ACM」に発表したものです。同じ年、Stephen Warshallもこのアルゴリズムを独自に発表しています。 Robert W. Floydこの牛は奇妙な男で、もともとシカゴ大学で文学を読んでいたのですが、アメリカの経済があまり豊かでなかったため、仕事を見つける方が難しく、仕方なくウェスティングハウス・エレクトリック・カンパニーにコンピュータ・オペレータとして、IBM 650マシンルームの夜勤に入り、こうして彼のキャリアが始まりました。コンピュータのキャリアをスタート。さらに、1964年にJ.W.J.ウィリアムズと共同で、第7章で研究する有名なヒープソートアルゴリズムHEAPSORTを発明しました。 ロバート・W・フロイドは、1987年にチューリング賞を受賞しました。
ブログのアドレス
