1. 概要

ベルマンフォードアルゴリズムは、加重グラフ内の1つのノードから他のすべてのノードへの最短経路を見つけるために使用される非常に一般的なアルゴリズムです。

このチュートリアルでは、ベルマンフォードアルゴリズムについて詳しく説明します。 動機、アルゴリズムのステップ、いくつかの実行例、およびアルゴリズムの時間計算量について説明します。

2. 動機

Bellman-Fordアルゴリズムは、単一ソース最短パスアルゴリズムです。 これは、重み付きグラフが与えられた場合、このアルゴリズムは選択されたノードから他のすべてのノードまでの最短距離を出力することを意味します。

これは、ダイクストラアルゴリズムと非常によく似ています。 ただし、ダイクストラアルゴリズムとは異なり、ベルマンフォードアルゴリズムは、負の重みのエッジを持つグラフで機能します。 この機能により、ベルマンフォードアルゴリズムが一般的な選択肢になります。

3. ネガティブエッジを考慮することが重要なのはなぜですか？

グラフ理論では、負のエッジは特定のグラフに負のサイクルを作成する可能性があるため、より重要です。 負のサイクルを持つ単純な重み付きグラフから始めて、あるノードから別のノードまでの最短距離を見つけてみましょう。

各ノードを都市と見なしています。 M市からR市に行きたいです。

M市からR市に到達するための3つの道路があります：MNPR、MNQPR、MNOPR。 道路の長さは5、2、8です。

しかし、詳しく見ると、負のサイクルがあることがわかります。長さが-1のNQPです。 したがって、パスNQPをカバーするたびに、道路の長さが短くなります。

道路NQPを無限に繰り返すことは、定義上、最も安価なルートであるため、これにより、最短経路で正確な答えを得ることができなくなります。

4. ベルマンフォードアルゴリズムのステップ

このセクションでは、ベルマンフォードアルゴリズムの手順について説明します。

その擬似コードから始めましょう：

このアルゴリズムは、入力として有向加重グラフと開始頂点を取ります。 開始頂点から他のすべての頂点までのすべての最短経路を生成します。

次に、擬似コードで使用した表記について説明します。 最初のステップは、頂点を初期化することです。 アルゴリズムは最初に、開始頂点から他のすべての頂点までの距離を無限大に設定します。 開始頂点からそれ自体までの距離は0です。 変数D[] は、このアルゴリズムの距離を示します。

初期化ステップの後、アルゴリズムは開始頂点から他のすべての頂点までの最短距離の計算を開始しました。 このステップは時間を実行します。 このステップ内で、アルゴリズムは他の頂点に到達するためにさまざまなパスを探索し、距離を計算しようとします。 アルゴリズムが以前に保存された値よりも小さい頂点の距離を検出すると、エッジを緩和して新しい値を保存します。

最後に、アルゴリズムが時間を繰り返し、必要なすべてのエッジを緩和すると、アルゴリズムはグラフに負のサイクルがあるかどうかを確認するための最後のチェックを行います。

負のサイクルが存在する場合、距離は減少し続けます。 このような場合、アルゴリズムは終了し、グラフに負のサイクルが含まれているという出力が得られるため、アルゴリズムは最短経路を計算できません。 負のサイクルが見つからない場合、アルゴリズムは最短距離を返します。

ベルマンフォードアルゴリズムは、動的計画法の例です。 開始頂点から開始し、1つのエッジが到達できる他の頂点の距離を計算します。 次に、2つのエッジを持つパスを検索し続けます。 Bellman-Fordアルゴリズムは、ボトムアップアプローチに従います。

5. 例

5.1. 負のサイクルのないグラフ

単純な有向グラフを使用して、ベルマンフォードアルゴリズムがどのように機能するかを視覚的に理解してみましょう。

Sが開始頂点であると仮定します。 これで、アルゴリズムの初期化ステップを開始する準備が整いました。

赤の値は距離を示します。 すでに説明したように、開始ノードから開始ノードまでの距離は0です。 他のすべての頂点の距離は、初期化ステップでは無限です。

ここには6つの頂点があります。 したがって、アルゴリズムは最短パスを見つけるために5回の反復を実行し、負のサイクルが存在する場合はそれを見つけるために1回の反復を実行します。

グラフを初期化した後、最初の反復に進むことができます。

一部の頂点の距離値が初期化ステップとは異なることがわかります。 距離の値がどのように更新されているかを調べてみましょう。 アルゴリズムは各エッジを選択し、それを関数 Relax（）に渡します。 まず、エッジ（S、A）について、 Relax（S、A）関数がどのように機能するかを見てみましょう。 最初に状態をチェックします。

エッジ（S、A）はチェック条件を満たすため、頂点Aは新しい距離を取得します。

これで、頂点Aの新しい距離値は10になります。 2番目のエッジは（A、B）です。 この場合も、このエッジは同じステップを通過します。 アルゴリズムはこのエッジをRelax（）に渡し、エッジはチェックステップを通過します。

エッジ（A、B）はチェック条件に合格し、新しい値を取得します。

このようにして、アルゴリズムはすべてのエッジを Relax（）に渡し、エッジが満たされると、頂点は新しい値を取得します。 ここで重要な点の1つは、考慮されるエッジのシーケンスです。 エッジのシーケンスに応じて、反復後に頂点の距離値が異なる場合があります。 これは絶対に問題ありません。 混乱を避けるために、この例で従ったエッジの順序をリストします。

（S、A）->（S、E）->（A、C）->（B、A）->（C、B）->（D、C）->（D、A）->（ E、D）

これで、最初の反復が完了しました。 2回目の反復後にグラフがどのように変化するかを見てみましょう。

反復1から、距離値に2つの変化があることがわかります。 さらに調査して、エッジリストを1つずつ見ていきましょう。 エッジ（S、A）、（S、E）、（A、C）、（B、A）、（C、B）、（E、D）がチェック条件を満たしていません。 したがって、距離の値は変更されません。 エッジ（D、C）、および（D、A）は条件を満たす。 エッジ（D、C）の場合：

したがって、アルゴリズムは頂点Cの新しい値を更新します。

エッジ（D、A）を確認しましょう：

アルゴリズムは頂点Aの新しい値を更新します。

これで、3番目の反復に進む準備ができました。

3回目の反復では、最後の反復からの距離値に2つの変更があります。 エッジ（S、A）、（S、E）、（B、A）、（D、C）、（D、A）、（E、D）はチェック条件を満たさないため、変更されません。 エッジ（A、C）と（C、B）は条件を満たしています。 エッジ（A、C）の場合：

したがって、頂点Cの新しい値が更新されます。

再びエッジ（C、B）の場合：

したがって、Bの新しい値が格納されます。

次に、4番目の反復に進みましょう。

4回目の反復後、頂点の距離値は更新されません。 これは、アルゴリズムが最終結果を生成することを意味します。 ここで、5つの相互作用に対してこのアルゴリズムを実行する必要があることを説明しました。 しかし、この場合、4の後に結果が得られました。

一般に、連続する反復の距離値が安定していない場合に実行する必要がある反復の最大数です。 この場合、2回の連続した反復で同じ値が得られたため、アルゴリズムは終了します。

5.2. 負のサイクルのグラフ

このセクションでは、負のサイクルを持つ別の重み付き有向グラフを使用します。ベルマンフォードアルゴリズムを実行して、アルゴリズムが負のサイクルを検出するかどうかを確認します。

グラフには4つの頂点があります。 ここでは、頂点Aを開始頂点と見なしています。 アルゴリズムは、最短距離の計算のために3回反復し、負のサイクルをチェックするためにもう1回反復することを想定しています。 ここで従うエッジの順序は次のとおりです。（D、B）->（C、D）->（A、C）->（A、B）->（B、C）

最初のステップは、グラフを初期化することです。

初期化が完了したら、最初の反復に進むことができます。

最初の反復の後、BとCの距離値の変化を確認できます。 頂点Aから、エッジの重みが頂点BとCに直接割り当てられ、距離の値が更新されます。 エッジ（A、C）の場合：

したがって、頂点Cの新しい値が更新されます。

同様にエッジ（A、B）の場合：

アルゴリズムはBの新しい値を保存します。

2回目の反復後に値がどのように変化するかを見てみましょう。

2回目の反復の後、頂点Dの距離値は、エッジ（C、D）を緩和することによってアルゴリズムによって更新されます。

したがって、頂点Cの新しい値が更新されます。

3回目の反復の後、値は再び変更されます。

ここに2つの更新があります。 1つは頂点B用で、もう1つは頂点C用です。 頂点Bの更新は、エッジ（D、B）を緩和することによって行われます。

したがって、頂点Bの新しい値が更新されます。

アルゴリズムは、エッジ（B、C）を緩和することにより、頂点Bの値を更新しました。

Cの値が更新され、保存されます。

必要な最大の反復が完了しました。 最後にもう一度繰り返して、グラフに負のサイクルがあるかどうかを判断しましょう。

頂点Dの値に変化があることがわかります。 アルゴリズムがエッジ（C、D）を緩和すると、変更が発生します。

Cの値が更新され、保存されます。

最大反復回数の後でも、距離値は安定していません。 したがって、この場合、アルゴリズムはグラフに負の重み付きサイクルが含まれていることを返します。したがって、開始頂点から指定されたグラフ内の他のすべての頂点までの最短経路を計算することはできません。

6. 時間計算量分析

最後に、ベルマンフォード法の時間計算量について見ていきます。

まず、初期化ステップで。

次に、アルゴリズムは時間を繰り返し、各反復には時間がかかります。

相互作用の後、アルゴリズムはすべてのエッジを選択し、エッジを Relax（）に渡します。 すべてのエッジの選択には時間がかかり、関数 Relax（）には時間がかかります。

したがって、すべての操作を実行する複雑さには時間がかかります。

Relax（）関数内で、アルゴリズムはエッジのペアを取得し、チェックステップを実行し、満たされた場合は新しい重みを割り当てます。 これらの操作はすべて時間がかかります。

したがって、ベルマンフォードアルゴリズムの合計時間は、初期化時間、 for ループ時間、およびリラックス関数時間の合計です。 合計すると、ベルマンフォードアルゴリズムの時間計算量はです。

7. 結論

この記事では、ベルマンフォードアルゴリズムについて詳しく説明しました。アルゴリズムの手順について説明し、2つの異なるグラフでアルゴリズムを実行して、読者に完全な理解を提供しました。 また、ネガティブエッジを考慮することが重要である理由を検討しました。

最後に、アルゴリズムの時間計算量を分析しました。