最短パスのDijkstraアルゴリズム
1508 ワード
•最短パスのFloydアルゴリズム•最短パスのBellmanアルゴリズム
Dijkstraアルゴリズムは、単一ソースの最短パスを解くために使用され、すなわち、指定された頂点sから残りの各頂点までの最短パスを求める.
この最短パスは、アルゴリズムの開始からアルゴリズムの終了までの間、dis配列内の値を最短パスの「推定値」と呼ぶdis配列で表されます.
最初は,原点sから自分への最短経路を0,すなわちdis[s]=0とした.そして、原点sが頂点iに直接到達可能であれば、dis[i]をsからiまでの距離であるdis[i]=e[s][i]に設定する.存在しない場合はdis[i]を「無限大」に設定
我々はすべての頂点を2つの集合に分け,1つは既知の最短経路の頂点集合P,1つは未知の最短経路の頂点集合Qである.Dijkstraアルゴリズムの核心思想は,集合Qからsに最も近い頂点u(dis[u]が最小)を1つずつ探し,集合Pにuを加え,uを起点としてvを終点とするすべてのエッジ(vはuに接続されたエッジの終点)を検索し,dis[v]>dis[u]+e[u][v]が成立するか否かを判断することである.成立するとdis[v]=dis[u]+e[u][v](この判定更新フローを「弛緩」と呼ぶ)が更新される.
そして、集合Qが空になるまで上記の手順を繰り返し、アルゴリズムが終了する.
コアコード
Dijkstraアルゴリズムは頂点と密接に関係しており,稠密図に適しており,全時間複雑度はO(N)である.²).sに最も近い頂点uを探す部分のコードをスタックで最適化すると時間的複雑度はO(Nlogn)に下げることができ,隣接テーブルで図を格納すると時間的複雑度はO((M+N)logn)に下がる.Dijkstraアルゴリズムは貪欲な戦略に基づくアルゴリズムであるため,すべての辺権が正の場合,より短い距離の点は存在しないため,集合Pに加えられたすべての点のdis値は二度と変化せず,この特徴に基づいてさらに外に拡張すると,新しい拡張の経路が最も短いことが保証される.負のエッジが存在する場合、負のエッジに拡張するとより短いパスが生成され、更新されたポイントパスが変更されない性質を破壊し、最終的には誤った結果を招く可能性があります.したがってDijkstraは負の重みエッジが存在する図には適用されず,負の重み回路も処理できない.
Dijkstraアルゴリズムは、単一ソースの最短パスを解くために使用され、すなわち、指定された頂点sから残りの各頂点までの最短パスを求める.
この最短パスは、アルゴリズムの開始からアルゴリズムの終了までの間、dis配列内の値を最短パスの「推定値」と呼ぶdis配列で表されます.
最初は,原点sから自分への最短経路を0,すなわちdis[s]=0とした.そして、原点sが頂点iに直接到達可能であれば、dis[i]をsからiまでの距離であるdis[i]=e[s][i]に設定する.存在しない場合はdis[i]を「無限大」に設定
我々はすべての頂点を2つの集合に分け,1つは既知の最短経路の頂点集合P,1つは未知の最短経路の頂点集合Qである.Dijkstraアルゴリズムの核心思想は,集合Qからsに最も近い頂点u(dis[u]が最小)を1つずつ探し,集合Pにuを加え,uを起点としてvを終点とするすべてのエッジ(vはuに接続されたエッジの終点)を検索し,dis[v]>dis[u]+e[u][v]が成立するか否かを判断することである.成立するとdis[v]=dis[u]+e[u][v](この判定更新フローを「弛緩」と呼ぶ)が更新される.
そして、集合Qが空になるまで上記の手順を繰り返し、アルゴリズムが終了する.
コアコード
// 1 s
book[1] = 1;
for (int i = 1; i < n; i++) // 1 P， n-1
{
int u, min=0xffff;
for (int j = 1; j <= n; j++)
if(!book[j] && min > dis[j])
{
min=dis[j];
u=j;
}
book[u]=1;
for (int v = 1; v <= n; v++)
//
if(e[u][v] != 0xffff && dis[v] > dis[u] + e[u][v])
dis[v] = dis[u] + e[u][v];
}
Dijkstraアルゴリズムは頂点と密接に関係しており,稠密図に適しており,全時間複雑度はO(N)である.²).sに最も近い頂点uを探す部分のコードをスタックで最適化すると時間的複雑度はO(Nlogn)に下げることができ,隣接テーブルで図を格納すると時間的複雑度はO((M+N)logn)に下がる.Dijkstraアルゴリズムは貪欲な戦略に基づくアルゴリズムであるため,すべての辺権が正の場合,より短い距離の点は存在しないため,集合Pに加えられたすべての点のdis値は二度と変化せず,この特徴に基づいてさらに外に拡張すると,新しい拡張の経路が最も短いことが保証される.負のエッジが存在する場合、負のエッジに拡張するとより短いパスが生成され、更新されたポイントパスが変更されない性質を破壊し、最終的には誤った結果を招く可能性があります.したがってDijkstraは負の重みエッジが存在する図には適用されず,負の重み回路も処理できない.