ベルマン・フォード法とは、グラフ理論において最短経路問題を解くためのアルゴリズムです。最短経路問題とは、ある頂点から別の頂点までの最も短い経路を見つける問題のことです。この記事では、ベルマン・フォード法について、中学生でも理解できるレベルで詳しく説明します。ベルマン・フォード法は、1956年にアメリカの数学者リチャード・ベルマンとエドワード・フォードによって提案されました。このアルゴリズムは、負の重みを持つ辺が存在するグラフにおいても最短経路を求めることができます。
さて、具体例を通じてベルマン・フォード法の仕組みを理解してみましょう。以下のようなグラフを考えます。
4 2
A ----► B ----► C
▲ ▲
│ │
│ 1 │ 3
│ │
D ----► E
-2
このグラフでは、頂点Aから頂点Cへの最短経路を求めたいとします。ベルマン・フォード法では、まず各頂点への距離を無限大に初期化します。そして、出発点からの距離を0に設定します。アルゴリズムの実行手順は以下の通りです。
- 全ての頂点の距離を無限大に初期化し、出発点の距離を0に設定します。
- 全ての辺に対して以下の操作を繰り返します。
- もし、辺の出発点の距離 + 辺の重み < 辺の到着点の距離 であれば、辺の到着点の距離を更新します。
- 2の操作をグラフの辺の数だけ繰り返します。
上記のグラフに対してベルマン・フォード法を適用してみましょう。
- AからAへの距離は0、他の頂点は無限大とします。
- 辺(A, B)の重みは4であり、AからBへの距離は0 + 4 = 4となります。
- 辺(A, D)の重みは1であり、AからDへの距離は0 + 1 = 1となります。
- 辺(B, C)の重みは2であり、BからCへの距離は4 + 2 = 6となります。
- 辺(B, E)の重みは3であり、BからEへの距離は4 + 3 = 7となります。
- 辺(D, E)の重みは-2であり、DからEへの距離は1 + (-2) = -1となります。 これで1回目の操作が終了しました。次に2回目の操作を行います。
- 辺(A, B)の重みは4であり、AからBへの距離は4ですが、既存の距離（4）よりも1回目の操作で求めた距離（4）の方が小さいため、距離は更新されません。
- 辺(A, D)の重みは1であり、AからDへの距離は1ですが、既存の距離（1）よりも1回目の操作で求めた距離（1）の方が小さいため、距離は更新されません。
- 辺(B, C)の重みは2であり、BからCへの距離は6ですが、既存の距離（6）よりも1回目の操作で求めた距離（6）の方が小さいため、距離は更新されません。
- 辺(B, E)の重みは3であり、BからEへの距離は7ですが、既存の距離（7）よりも1回目の操作で求めた距離（7）の方が小さいため、距離は更新されません。
- 辺(D, E)の重みは-2であり、DからEへの距離は-1ですが、既存の距離（-1）よりも1回目の操作で求めた距離（-1）の方が小さいため、距離は更新されません。
このように、2回目の操作では距離の更新は行われず、最終的な結果は以下のようになります。
- 頂点Aから頂点Aへの最短距離は0
- 頂点Aから頂点Bへの最短距離は4
- 頂点Aから頂点Cへの最短距離は6
- 頂点Aから頂点Dへの最短距離は1
- 頂点Aから頂点Eへの最短距離は-1
まとめ
ベルマン・フォード法では、辺の数に比例して操作を繰り返すため、計算量が大きくなる可能性があります。この特徴を持つ一方で、ベルマン・フォード法の利点は、負の重みを持つ辺にも対応できることです。
最悪の場合、ベルマン・フォード法では辺の数をEとすると、E回の操作が必要となります。このため、グラフが非常に大きくなると計算時間が増える可能性があります。しかし、他の最短経路アルゴリズムよりも負の重みに対応できるため、特定の問題においては有用です。
負の重みを持つ辺が存在する場合、最短経路を求める際には正しく結果を得るために全ての辺に対して操作を繰り返す必要があります。これにより、負の重みが経路の総和を小さくする可能性があるため、正しい最短経路を求めることができます。
ただし、一般的な場合においては、負の重みを持つ辺が多い場合や、辺の数が非常に大きい場合には計算時間が増えることがあります。そのため、実際の問題においては、最短経路問題の性質や制約を考慮して、適切なアルゴリズムを選択する必要があります。
以上のように、ベルマン・フォード法は計算量の面では注意が必要ですが、負の重みに対応できる利点があります。そのため、特定の問題においては有用なアルゴリズムと言えます。ベルマン・フォード法のPythonでの実装は下記の記事で紹介しています。
