最短経路アルゴリズム

頂点から始まり、グラフのエッジに沿って別の頂点に到達するパスのうち、各エッジの重みの合計が最小となるパスを最短パスと呼びます。最短経路問題を解くアルゴリズムには、ダイクストラアルゴリズム、ベルマンフォードアルゴリズム、フロイドアルゴリズム、SPFAアルゴリズムなどがあります。

#定義

最短経路問題は、グラフ ( 2 つのノード間の最短パス (ノードとパスで構成される)。アルゴリズムの具体的な形式は次のとおりです。

(1) 開始点からの最短経路を決定する問題、つまり、開始ノードが既知の場合の最短経路を見つける問題。ダイクストラアルゴリズムの使用に適しています。 (推奨学習:

PHP ビデオ チュートリアル )

(2) 終点までの最短経路を求める問題 - 始点を求める問題とは逆に、この問題は終了ノードが既知の場合の最短パスについての質問です。無向グラフではこの問題は始点を求める問題と全く等価ですが、有向グラフではすべてのパスの方向を反転して始点を求める問題と等価です。

(3) 始点と終点の間の最短経路を決定する問題。つまり、始点と終点が与えられた場合に、2 つのノード間の最短経路を見つけます。

(4) 全体的な最短経路の問題 - グラフ内のすべての最短経路を見つけます。 Floyd-Warshall アルゴリズムの使用に適しています。

Dijkstra

ソースが 1 つで、負の重みがない最短パスを見つけます。適時性は良好で、時間計算量は O(V*V E) です。ソース点に到達可能な場合は、O(V*lgV E*lgV) =>O(E*lgV) となります。

スパース グラフの場合、E=V*V/lgV となるため、アルゴリズムの時間計算量は O(V^2) になります。フィボナッチ ヒープが優先キューとして使用される場合、アルゴリズムの時間計算量は O(V*lgV E) になります。

Floyd

複数のソースを持ち、負の重みエッジがない最短パスを見つけます。マトリックスを使用してグラフを記録します。適時性は悪く、時間計算量は O(V^3) です。

Floyd-Warshall アルゴリズム (Floyd-Warshall アルゴリズム) は、任意の 2 点間の最短経路を解くアルゴリズムであり、有向グラフや負の重みの最短経路問題を正しく処理できます。

Bellman-Ford

単一ソースから最短パスを見つけるには、負の重みループがあるかどうかを判断できます (ある場合は、負の重みループはありません)。最短パス)、

適時性が向上、時間計算量 O(VE)。

Bellman-Ford アルゴリズムは、単一ソース最短経路問題を解決するためのアルゴリズムです。

SPFA

は Bellman-Ford のキュー最適化であり、適時性が比較的高く、時間計算量は O(kE) です。 (kベルマンフォード アルゴリズムと同様に、SPFA アルゴリズムは一連の緩和操作を使用して、グラフ内の特定のノードから他のすべてのノードへの最短パスを取得します。違いは、SPFA アルゴリズムがキューを維持するため、ノードの現在の最短パスが更新された後、他のノードをすぐに更新する必要がないため、反復操作の数が大幅に削減されることです。

PHP 関連の技術記事をさらに詳しく知りたい場合は、

PHP グラフィック チュートリアル 列にアクセスして学習してください。

以上が最短経路アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。