フロイドアルゴリズムの原理は何ですか?

フロイド アルゴリズムの原理は、動的計画法の考え方を使用して、指定された重み付きグラフ内の複数のソース ポイント間の最短経路を見つけるアルゴリズムです。ダイクストラ アルゴリズムに似ています。動的プログラミングの考え方を使用して、指定された重み付きグラフ内の複数のソース ポイント間の最短パスを見つけるアルゴリズム。重み付けされたグラフ内の最短パスを見つけるためのアルゴリズム。

Floyd アルゴリズム 補間法とも呼ばれ、動的計画法の考え方を利用して複数のソースを見つける方法です。指定された重み付きグラフでの点間の最短経路のアルゴリズムは、ダイクストラのアルゴリズムに似ています。このアルゴリズムは、創設者の 1 人であり、1978 年チューリング賞受賞者であり、スタンフォード大学コンピューター サイエンス教授であるロバート フロイドにちなんで名付けられました。

コンピューター サイエンスにおいて、フロイド-ウォーシャル アルゴリズムは、最短経路を見つけるためのアルゴリズムです。正または負のエッジ重みを持つ重み付きグラフ (ただし、負の期間はありません)。アルゴリズムを 1 回実行すると、すべての頂点ペア間の最短パスの長さ (重み付き) が見つかります。パス自体の詳細は返されませんが、アルゴリズムを簡単に変更することでパスを再構築できます。このアルゴリズムのバージョンは、関係 R の推移閉包、または (シュルツ投票システムに関連して) 重み付きグラフ内の頂点のすべてのペア間の最も広いパスを見つけるために使用することもできます。

フロイド-ウォーシャル アルゴリズムは動的プログラミングの一例であり、現在受け入れられている形式で Robert Floyd によって 1962 年に公開されました。ただし、これは、1959 年に Bernard Roy と 1962 年に Stephen Warshall によって以前に発表されたグラフの推移閉包を見つけるためのアルゴリズムと本質的に同じであり、決定論的有限オートマトンを正規表現に変換するための 1956 年の Kleene のアルゴリズムと密接に関連しています。 3 つのネストされた for ループとしてのアルゴリズムの最新の定式化は、1962 年に Peter Ingerman によって初めて説明されました。

このアルゴリズムは、フロイド アルゴリズム、ロイ-ウォーシャル アルゴリズム、ロイ-フロイド アルゴリズム、または WFI アルゴリズムとも呼ばれます。

コアアイデア編集

1. パス行列

グラフの重み行列を 2 つずつ検索します 点間の最短パス行列。

グラフの重み付き隣接行列 A=[a(i,j)] n×n から開始して、a に従って、行列 D(0)=A から n 回の更新を再帰的に実行します。式、構築 行列 D(1) が取得されます。同じ式を使用して D(1) から D(2) が構築されます。...; 最後に、行列 D(n) が D(n-1) から構築されます。 )同じ式を使用します。行列 D(n) の i 行 j 列の要素は、頂点 i から頂点 j までの最短経路長です。D(n) はグラフの距離行列と呼ばれます。同時に、後続ノードの行列パスは、 2 点間の距離、つまり最短経路を記録するためにも導入されます。

リラクゼーション技術 (リラクゼーション操作) を使用して、i と j の間の他のすべての点をリラックスさせます。したがって、時間計算量は O(n^3);

2 状態遷移方程式

状態遷移方程式は次のとおりです:map[i,j]: =min {map[i,k] map[k,j],map[i,j]};

map[i,j] は i から j までの最短距離を表し、K は網羅的な距離を表しますi,j ブレークポイントのリスト、map[n,n] の初期値は 0 であるか、質問の意味に従ってください。

もちろん、この道路がアクセスできない場合は、特別な処理を実行する必要があります。たとえば、map[i,k] 道路がありません。

アルゴリズム プロセス エディター

1、任意の一方的なパスから開始します。すべての 2 点間の距離がエッジの重みになります。2 点を結ぶエッジが存在しない場合、重みは無限大になります。

2、頂点 u と v の各ペアについて、u から w、v までのパスが既知のパスよりも短くなるような頂点 w があるかどうかを確認します。その場合は更新してください。

グラフを隣接行列 G として表します。Vi から Vj へのパスがある場合、G[i][j]=d、d はパスの長さを表し、それ以外の場合は G[i][ j ] = 無限大。挿入された点の情報を記録する行列 D を定義します。D[i][j] は Vi から Vj に渡す必要がある点を表します。D[i][j]=j を初期化します。各頂点をグラフに挿入し、挿入後の距離を元の距離と比較します。 G[i][j] = min( G[i][j], G[i][k] G[k][j] ）、G[i][j]の値が小さくなると、D[i][j]=kとなります。 G には 2 点間の最短道路の情報が含まれ、D には最短経路の情報が含まれます。

たとえば、V5 から V1 へのパスを見つけたいとします。 D によれば、D(5,1)=3 の場合、V5 から V1 への経路は V3 を経由することを意味し、D(5,3)=3 の場合、V5 とV3 は直接接続されています D (3,1)=1 の場合、V3 と V1 が直接接続されていることを示します。

時間計算量と空間計算量の編集

時間計算量: O(n ^ 3);

空間計算量: O(n ^ 2)

長所と短所の分析と編集

#Floyd アルゴリズムは、APSP (全ペア最短パス、マルチソース最短パス) に適しており、動的プログラミング アルゴリズムであり、高密度です。グラフが最も効果的であり、エッジの重みは正または負になります。このアルゴリズムはシンプルで効果的であり、コンパクトな三重ループ構造により、密なグラフの場合、ダイクストラアルゴリズムの |V| 回実行よりも効率が高く、SPFA アルゴリズムの |V| 回実行よりも効率が高くなります。

利点: 理解しやすく、任意の 2 つのノード間の最短距離を計算でき、コードの記述も簡単です。

欠点: 時間計算量は比較的高く、大量のデータの計算には適していません。

以上がフロイドアルゴリズムの原理は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。