SPFA アルゴリズムの使用チュートリアル

適用範囲: 特定のグラフに負の重みエッジが存在する場合、ダイクストラなどのアルゴリズムを使用する余地がなく、ベルマン-フォード アルゴリズムの複雑さが高すぎるため、SPFA アルゴリズムが役に立ちます。 。 有向重み付きグラフ G には負の重みサイクルが存在しない、つまり最短経路が存在する必要があることに同意します。もちろん、負の重みサイクルがあるかどうかを判断するためにアルゴリズムを実行する前にトポロジカルなソートを行うこともできますが、これはここでの議論の焦点では​​ありません。

アルゴリズムのアイデア: 配列 d を使用して各ノードの最短パス推定を記録し、隣接リストを使用してグラフ G を保存します。私たちが採用する方法は動的近似法です。最適化の際に、先入れ先出しキューを設定して最適化するノードを保存し、毎回ヘッド ノード u を取り出し、現在の最短パス推定値を使用します。ポイント u からポイント u を離れる。ポイント v の最短パス推定が調整され、ポイント v が現在のキューにない場合、ポイント v はキューの最後に配置されます。このようにして、キューが空になるまでノードがキューから継続的に取り出され、緩和操作が実行されます。ここで、k はすべての頂点がキューに入る平均回数です。 k は通常 2 以下です。

実装方法:

最初はキューに始点のみを作成し、始点からすべての点までの最短経路を記録するテーブルを作成します。テーブルの初期値は極値に割り当てる必要があります。値が大きい場合、この点からそれ自体までのパスには 0 が割り当てられます。次に、キュー内のいくつかのポイントを開始点として使用して緩和操作を実行し、すべてのポイントへの最短パスをリフレッシュします。リフレッシュが成功し、リフレッシュされたポイントがキュー内にない場合、そのポイントはキューの最後に追加されます。 。キューが空になるまで繰り返します。

負のサイクルがあるかどうかを判断します。

ポイントが N 回以上キューに入った場合、負のサイクルが存在します (SPFA は負のサイクルを持つグラフを処理できません)

建建建

最初の始点 A から残りの点の最短経路テーブルまでのとき:

1. 1つ目チームの要素(a)をデキューし、aを始点としてすべての辺の終点(ここではb、c、dの3点)に対して緩和操作を行います。このときのパステーブルは次のようになります。 status For: 松

リラックス時の 3 つのポイントの最短経路の評価が小さくなり、これらのキューはいずれも表示されません。 この時点で、これらのポイントはチームに新たに入力する必要があります。 3 つのノード b、c、d がキューに入れられ、最初の要素 b がデキューされ、b を始点としてすべてのエッジの終点に対して緩和操作が実行されます (ここでは点 e のみです)。今回のパステーブルの状態は

短 最短パステーブルでは E の最短パス評価がキューに存在しないため、この時点で E もチームに入らなければなりません。 、キュー内 の要素は c、d、e で​​す

チームの最初の要素はポイント c でデキューされ、c を開始点としてすべてのエッジの終点で緩和操作が実行されます (そこにここでは 2 つの点 e と f) は、この時点でのフォームのステータスは次のとおりです:

径・最短パステーブルでは、E、Fの最短パス評価が小さくなり、Eはキューに存在し、Fは存在しません。したがって、

eはキューに参加する必要はなく、fはキューに参加する必要があります。このとき、キュー内の要素はd、e、fです

チームの最初の要素がキューから外れます。点 d、および d を始点とするすべてのエッジの終点で緩和操作を順番に実行します (ここには点 g のみがあります)。この時点で、パス テーブルのステータスは次のようになります。
最短経路テーブルでは、g の最短経路推定値は小さくなりません (緩和は失敗)、新しいノードはキューに入りません、キュー内の要素は f、g

の最初の要素ですチームは点 f でデキューされ、f を始点とするすべてのエッジの終点が順番に緩和されます (ここでは 3 つの点 d、e、g があります)。このとき、パス テーブルのステータスは次のようになります。

点 e はなく、キュー内に点 g があり、キュー内に g がある必要はありません。 このとき、キュー内の要素は g であり、キューの最初の要素であるポイント g はキューの外にあり、g を始点とするすべてのエッジの終点が順に緩和されます (この時点では、 の状態は B のみです)。パステーブルは、

最短パステーブルでは、B の最短パスの評価が小さくなり、キューに B が存在しません。 このとき、要素はキューに入ります。キュー内には e があり、チーム b

点 e の最初の要素がキューから出ます。緩和操作は、始点としてすべてのエッジの終点で実行されます (ここには点 g のみがあります)。このとき、パス テーブルのステータスは次のとおりです。

この時点で、最短パス テーブルでは、G の最短パスの評価は変更されていません (失敗)。キューは B

チームの最初の要素である点 b がデキューされ、b を始点としてすべてのエッジの終点に対して緩和操作が実行されます (ここでは点 e のみです)。この時点で、パス テーブルのステータスは次のとおりです。

最短パス テーブルでは、e の最短パス推定値は変更されておらず (緩和は失敗しました)、この時点ではキューは空です

aからgまでは14

javaコード

りー

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