Motivation
Coddyの「ベルマン–フォード法 - グラフアルゴリズム」コースのレッスン 2/9。
ベルマン–フォード法は、1つの操作、緩和（relaxation）に基づいています。重み w のエッジ u -> v に対して、u を経由する方が低コスト（dist[u] + w < dist[v]）であれば、dist[v] を更新します。これをすべてのエッジに対して繰り返し行います。
なぜベルマン–フォード法を学ぶのか？
- 負の重み: ダイクストラ法が使えないケース（例：払い戻しや通貨の裁定取引など、コストが負になり得る場合）でも動作します。
- 負の閉路の検出: 緩和をもう1回追加で行うことで、合計の重みが負になる閉路を見つけることができます。
- シンプルさ: 優先度付きキューは不要で、エッジの緩和を繰り返すだけです。
トレードオフは速度です。O(V * E) であり、ダイクストラ法の O((V + E) log V) よりも低速です。
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
