【便器の上に座ってアルゴリズムを見る】アルゴリズム7:Dijkstraの最短アルゴリズム
7125 ワード
先週は不思議な5行のFloydショートアルゴリズムを紹介しました.任意の2点の最短経路を簡単に求めることができます.これを「多源一番短絡」といいます.今週は、1つのポイント(ソースポイント)から残りの各頂点までの最短ルートを紹介します.いわゆる「単一ソース最短経路」です.例えば、下の図の1番の頂点から2、3、4、5、6番の頂点までの最短ルートを求めます.
Floyd-Warshallアルゴリズムと同様に、ここでは依然として2次元配列eを使用して頂点間の関係を記憶しています.初期値は以下の通りです.
私たちはまた1次元配列disを用いて、1番の頂点から残りの各頂点までの初期道のりを保存します.
この時のdis配列の値を、最も短絡的な「推定値」と呼びます.
1番の頂点から他の各頂点までの最短距離を求めるなら、まず1番の頂点から一番近い頂点を探します.配列disによって、現在は1番の頂点から一番近いのが2番の頂点です.2番の頂点を選択したら、dis[2]の値はすでに「推定値」から「確定値」に変わりました.つまり、1番の頂点から2番の頂点までの最短距離は現在のdis[2]の値です.なぜですか?今1番の頂点から一番近いのは2番の頂点です.そして、この図のすべての端は正数ですから、3番目の頂点を経由して乗り換えることは不可能です.1番の頂点から2番の頂点までの道のりをさらに短縮しました.1番の頂点から他の頂点までの道のりはきっと1番から2番の頂点までは短いですよね.
2番の頂点を選んだ以上、次に2番の頂点にはどの辺がありますか?二つの辺があります.まず、2->>3の辺を通過して、1番の頂点から3番の頂点までの道のりを短くすることができますか?つまり今はdis[3]とdis[2]+e[2]、[3]の大きさを比較します.このうちdis[3]は1番の頂点から3番の頂点までの道のりを表します.dis[2]+e[2]、[3]でdis[2]は1番の頂点から2番の頂点までの道のりを示し、e[2][3]は2->3の辺を表します.だからdis[2]+e[2]、[3]は、1番の頂点から2番の頂点まで、2->3の辺を通って、3番の頂点までの道のりを表します.
私たちはdis[3]=12を発見しました.dis[2]+e[2]=[3]=1+9=10、dis[3]>dis[2]+e[3]を発見しましたので、dis[3]を10に更新します.この過程には専門用語があります.「緩和」といいます.つまり、1番の頂点から3番の頂点までの道のりがdis[3]であり、2->3の辺のたるみで成功しました.これはDijkstraアルゴリズムの主な思想です.「辺」を通じて1番の頂点から残りの各頂点までの道のりを緩和します.
2->4(e[2][4])により、dis[4]の値を∞から4(dis[4]は∞、dis[2]+e[4]=1+3=4、dis[4]>dis[2]+e[4]に緩和することができますので、dis[4]は4に更新します.
先ほど私たちは2番の頂点のすべてのエッジを緩和しました.緩和が完了したらdis配列は次のようになります.
次に、残りの3、4、5、6番の頂点のうち、1番の頂点から一番近い頂点を選びます.上でdis配列を更新しました.現在は1番の頂点から一番近いのは4番の頂点です.このとき、dis[4]の値はすでに「推定値」から「決定値」に変化している.4番の頂点のすべてのエッジ(4->>3,4->5,4->6)を先ほどの方法で緩和し続けます.緩和が完了したらdis配列は次のようになります.
残りの3、5、6番の頂点のうち、1番の頂点から一番近い頂点を選び続けます.今回は3番の頂点を選びます.このとき、dis[3]の値はすでに「推定値」から「決定値」に変わりました.3番の頂点のすべてのエッジ(3->5)を緩和します.緩和が完了したらdis配列は次のようになります.
残りの5番と6番の頂点のうち、1番の頂点から一番近い頂点を選びます.今回は5番の頂点を選びます.このとき、dis[5]の値はすでに「推定値」から「決定値」に変わりました.5番の頂点のすべてのエッジ(5->>4)を緩和します.緩和が完了したらdis配列は次のようになります.
最後に6番の頂点のすべての点を出して緩和します.この例では6番の頂点がエッジから外れていないので、処理は不要です.これにより、dis配列のすべての値が「推定値」から「決定値」に変わりました.
最終的なdis配列は、1番の頂点から残りの各頂点までの最短ルートです.
OKです.先ほどのアルゴリズムをまとめます.アルゴリズムの基本的な考え方は、ソースポイント(上の例のソースポイントは1番の頂点)から一番近い頂点を見つけ、その頂点を中心に拡張し、最終的にソースポイントから残りのすべての点までの最短ルートを得ることである.基本的な手順は以下の通りです.は、すべての頂点を2つの部分に分けます.最短距離が既知の頂点セットPと未知の最短経路の頂点セットQ.最初に、最も短い経路が知られている頂点セットPには、ソースポイントの頂点しかない.ここではbook[i]配列を使って集合Pにどのような点が記録されていますか?例えば、ある頂点iについて、book[i]が1であれば、この頂点はセットPにあり、book[i]が0であれば、この頂点はセットQにあることを示す. は、ソースポイントsから自分の最短経路が0であるdis=0を設定します.ソースポイントが直接到達できる頂点iがあれば、dis[i]をe[s][i]に設定する.他の全ての頂点の最短経路を∞に設定します. は、セットQのすべての頂点のうち、ソースポイントsから最も近い頂点u(すなわち、dis［u］最小)を選択して、セットPに参加する.そして点uを起点とするすべての辺を調べて,各辺に対して緩和操作を行った.例えば、uからvまでの辺があると、端u−vを尾部に追加してsからvまでの経路を拡張することができ、この経路の長さはdis［u］＋e［v］である.この値が現在知られているdis[v]の値より小さい場合、現在のdis[v]の値を新しい値で置き換えることができます. は、第3のステップを繰り返し、セットQが空の場合、アルゴリズムは終了する.最終的なdis配列の値は、ソースポイントからすべての頂点までの最短ルートです. 完全なDijkstraアルゴリズムコードは以下の通りです.
1
転載を歓迎して、コードワードは容易ではありませんて、転載して出所を明記します.http://ahalei.blog.51cto.com/4767671/1387799
Floyd-Warshallアルゴリズムと同様に、ここでは依然として2次元配列eを使用して頂点間の関係を記憶しています.初期値は以下の通りです.
私たちはまた1次元配列disを用いて、1番の頂点から残りの各頂点までの初期道のりを保存します.
この時のdis配列の値を、最も短絡的な「推定値」と呼びます.
1番の頂点から他の各頂点までの最短距離を求めるなら、まず1番の頂点から一番近い頂点を探します.配列disによって、現在は1番の頂点から一番近いのが2番の頂点です.2番の頂点を選択したら、dis[2]の値はすでに「推定値」から「確定値」に変わりました.つまり、1番の頂点から2番の頂点までの最短距離は現在のdis[2]の値です.なぜですか?今1番の頂点から一番近いのは2番の頂点です.そして、この図のすべての端は正数ですから、3番目の頂点を経由して乗り換えることは不可能です.1番の頂点から2番の頂点までの道のりをさらに短縮しました.1番の頂点から他の頂点までの道のりはきっと1番から2番の頂点までは短いですよね.
2番の頂点を選んだ以上、次に2番の頂点にはどの辺がありますか?二つの辺があります.まず、2->>3の辺を通過して、1番の頂点から3番の頂点までの道のりを短くすることができますか?つまり今はdis[3]とdis[2]+e[2]、[3]の大きさを比較します.このうちdis[3]は1番の頂点から3番の頂点までの道のりを表します.dis[2]+e[2]、[3]でdis[2]は1番の頂点から2番の頂点までの道のりを示し、e[2][3]は2->3の辺を表します.だからdis[2]+e[2]、[3]は、1番の頂点から2番の頂点まで、2->3の辺を通って、3番の頂点までの道のりを表します.
私たちはdis[3]=12を発見しました.dis[2]+e[2]=[3]=1+9=10、dis[3]>dis[2]+e[3]を発見しましたので、dis[3]を10に更新します.この過程には専門用語があります.「緩和」といいます.つまり、1番の頂点から3番の頂点までの道のりがdis[3]であり、2->3の辺のたるみで成功しました.これはDijkstraアルゴリズムの主な思想です.「辺」を通じて1番の頂点から残りの各頂点までの道のりを緩和します.
2->4(e[2][4])により、dis[4]の値を∞から4(dis[4]は∞、dis[2]+e[4]=1+3=4、dis[4]>dis[2]+e[4]に緩和することができますので、dis[4]は4に更新します.
先ほど私たちは2番の頂点のすべてのエッジを緩和しました.緩和が完了したらdis配列は次のようになります.
次に、残りの3、4、5、6番の頂点のうち、1番の頂点から一番近い頂点を選びます.上でdis配列を更新しました.現在は1番の頂点から一番近いのは4番の頂点です.このとき、dis[4]の値はすでに「推定値」から「決定値」に変化している.4番の頂点のすべてのエッジ(4->>3,4->5,4->6)を先ほどの方法で緩和し続けます.緩和が完了したらdis配列は次のようになります.
残りの3、5、6番の頂点のうち、1番の頂点から一番近い頂点を選び続けます.今回は3番の頂点を選びます.このとき、dis[3]の値はすでに「推定値」から「決定値」に変わりました.3番の頂点のすべてのエッジ(3->5)を緩和します.緩和が完了したらdis配列は次のようになります.
残りの5番と6番の頂点のうち、1番の頂点から一番近い頂点を選びます.今回は5番の頂点を選びます.このとき、dis[5]の値はすでに「推定値」から「決定値」に変わりました.5番の頂点のすべてのエッジ(5->>4)を緩和します.緩和が完了したらdis配列は次のようになります.
最後に6番の頂点のすべての点を出して緩和します.この例では6番の頂点がエッジから外れていないので、処理は不要です.これにより、dis配列のすべての値が「推定値」から「決定値」に変わりました.
最終的なdis配列は、1番の頂点から残りの各頂点までの最短ルートです.
OKです.先ほどのアルゴリズムをまとめます.アルゴリズムの基本的な考え方は、ソースポイント(上の例のソースポイントは1番の頂点)から一番近い頂点を見つけ、その頂点を中心に拡張し、最終的にソースポイントから残りのすべての点までの最短ルートを得ることである.基本的な手順は以下の通りです.
#include intmain(){ inte[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min; intinf=99999999; // inf(infinity ) // 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; elsee[i][j]=inf; // for(i=1;i<=m;i++) { scanf("%d %d %d",&t1,&t2,&t3); e[t1][t2]=t3; } // dis ， 1 for(i=1;i<=n;i++) dis[i]=e[1][i]; //book for(i=1;i<=n;i++) book[i]=0; book[1]=1; //Dijkstra for(i=1;i<=n-1;i++) { // 1 min=inf; for(j=1;j<=n;j++) { if(book[j]==0 && dis[j]
{ min=dis[j]; u=j; } } book[u]=1; for(v=1;v<=n;v++) { if(e[u][v]
{ if(dis[v]>dis[u]+e[u][v]) dis[v]=dis[u]+e[u][v]; } } } // for(i=1;i<=n;i++) printf("%d ",dis[i]); getchar(); getchar(); return0;} 以下のデータを入力して検証できます.最初の行の2つの整数n mです.nは頂点個数(頂点番号は1~n)を表し、mは辺の本数を表します.次にm行を表します.行には3つの数x y zがあります.頂点xから頂点yまでの権利値はzです.6 91 2 11 3 122 3 92 4 33 5 54 3 44 5 134 6 155 6 4 運転結果は1
0 1 8 4 13 17 上記のコードから,このアルゴリズムの時間複雑さはO(N 2)であることを示した.その中で毎回1番の頂点に一番近い頂点を見つける時間の複雑さはO(N)です.ここでは「積み上げ」を使って最適化して、この部分の時間複雑度をO(logN)に下げることができます.また、N 2以下の辺数Mの間引き図については(MがN 2以下の図を間引き図といい、Mが比較的大きい図を稠密図といいます)、隣接表(これは何ですか?焦らず、来週に詳しく説明します)を使って隣接マトリックスの代わりに、時間の複雑さをO(M＋N)logN)に最適化します.注意してください最悪の場合はMはN 2です.これでMlogNはN 2よりも大きいです.しかし、多くの場合はそれほど多くはないので、(M＋N)logNはN 2より小さいです.転載を歓迎して、コードワードは容易ではありませんて、転載して出所を明記します.http://ahalei.blog.51cto.com/4767671/1387799