最短ルートアルゴリズムのまとめ

最短ルートアルゴリズムのまとめ
Dijkstraアルゴリズム
Dijkstra(ディジェストラ)アルゴリズムは、1つのノードから他のすべてのノードへの最短パスを計算するための典型的な単一ソース最短パスアルゴリズムである.
最も一般的な問題は、地図を1枚あげて、指定した点から残りの各定点までの最短経路を求めることです.
アルゴリズムコア:ソースポイントに最も近い頂点が見つかるたびに、その頂点を中心に拡張され、最終的にはソースポイントから残りのすべてのポイントへの最短パスになります.アルゴリズムの時間的複雑度はO(N 2),空間的複雑度はO(N 3)である.
基本手順は次のとおりです.

はすべての頂点を2つの部分に分けている:既知の最短距離の頂点集合Pと未知の最短経路の頂点集合Q.最初に、最短パスが知られている頂点セットPには、ソースポイントと1つの頂点しかありません.ここでは,集合Pにどの点が存在するかをbook配列で記録する.例えば、ある頂点iについて、book[i]が1であればその頂点が集合Pにあることを示し、book[i]が0であればその頂点が集合Qにあることを示す.

ソースポイントsから自分への最短パスを0、すなわちdis[s]=0に設定します.アクティブポイントが直接到達できる頂点iがあればdis[i]をe[s][i]とする.同時に他のすべての(ソースポイントが直接到達できない)頂点の最短経路を∞とする.

は、集合Qのすべての頂点のうち、ソース点sに最も近い頂点u(すなわち、dis[u]が最小)を選択して集合Pに加える.点uを起点とするすべてのエッジを考察し,各エッジに対して緩和操作を行った.例えば、uからvまでのエッジが存在する場合、エッジu→vをテールに追加することによって、dis[i]+e[u][v]の長さのsからvまでのパスを拡張することができる.この値が現在知られているdis[v]の値よりも小さい場合、現在のdis[v]の値を新しい値で置き換えることができます.

は第3のステップを繰り返し、集合Qが空の場合、アルゴリズムは終了する.最終dis配列の値は、ソースポイントからすべての頂点への最短パスです.

Dijkstraアルゴリズムのコアコード:

for (i = 1; i < n; i++) {//         
    min = inf; //   1        
    for (j = 1; j <= n; j++) {
        if (book[j] == 0 && dis[j] < min) {//book                  
            min = dis[j]; //  1 j     
            u = j; //     1       
        }
    }
    book[u] = 1; //          
    for (v = 0; v <= n; v++) {
        if (map[u][v] < inf) {//          v    inf
            if (dis[v] > dis[u] + e[u][v]) //     1 v       （1 u  u v）   ，      dis[v]  
                dis[v] = dis[u] + e[u][v];
        }
    }
}

Floydアルゴリズム
Floyd(フロイド)アルゴリズムは、任意の2点間の最短経路を解決するアルゴリズムであり、図面または負の重みを持つ最短経路問題を正しく処理することができる.
最も一般的な問題は、地図を1枚あげて、任意の2点の間の最短経路を求めることです.
アルゴリズムコア:iからjの最短距離を更新するために1つの点kを導入するたびに、任意の2点間の最短距離を求める.
アルゴリズムの時間的複雑度はO(N 3),空間的複雑度はO(N 2)である.
基本手順は次のとおりです.

は、任意の片側パスから始まり、すべての2点間の距離はエッジの重みであり、2点間にエッジが接続されていない場合、重みは無限大である.

各ペアの頂点uおよびvについて、uからwへ、およびvへの経路が既知の経路よりも短くなるように、頂点wが存在するかどうかを確認し、それを更新する場合.

すべての頂点について、すべての頂点を巡回するまで、上記の操作を繰り返します.

Floydアルゴリズムコアコード:

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]) //  i j        i k  k j,   e[i][j]  
                e[i][j] = e[i][k] + e[k][j];