- ベルマンフォード法って何？
- ダイクストラ法との違いは？
- どんな方法で解いたらいいの？
- Pythonで実装するにはどうするの？
こんな悩みを解決できる記事になっています！
なぜなら、僕が大学でベルマンフォード法を勉強して、分からなかった部分を噛み砕いて説明するためです。
本記事の信頼性
ベルマンフォード法は以下のようなステップで最短経路を求める手法になります。
- 始点以外は距離が無限と仮定
- すべての点から最短距離を調査
- STEP2を(頂点数-1)回行い、最短距離を更新
- (頂点数)回更新されたら、負閉路があると判断
この記事を読み終えることで、ベルマンフォード法を解けるだけでなく、人に分かりやすく説明できるようになるでしょう。
記事の前半では『ベルマンフォード法のアルゴリズム』を紹介し、記事の後半では『ベルマンフォード法のPythonでの実装』を具体的に解説します。
「問題の解き方を早く知りたい！」という方は、『ベルマンフォード法のアルゴリズム』にジャンプしてください！
月額980円で学べる！
データサイエンスの復習は完ぺきにできていますか？
データサイエンスは勉強する範囲が膨大で、復習に手が回りませんよね。
そんなあなたにおすすめなのが、たった月額980円でサクッと学べる『スタアカ』
数分の動画でビジネスへの活用法も含めて、サクッとデータサイエンスを復習可能。
『何冊も参考書を往復して復習する苦労』とはおさらばです！
サブスクなのでいつでも解約OK。手軽に始めてみませんか？
＼月額980円から／
講座が毎月追加されるので今後値上がりする可能性大、今買わなきゃ損するかも！
それでは本編です！
ベルマンフォード法とは
ベルマンフォード法とは重み付きグラフの全頂点における始点からの最短距離を計算するアルゴリズムです。
負辺がある場合でも最短経路を見つけ出せるのが特徴で、負の閉路（ループ）があると最短経路は存在しないと判断されます。
例えば、地図上でいろいろな道を通って目的地までの最短ルートや費用を抑えたルートを探したい時にベルマンフォード法が用いられます。
ベルマンフォード法は、支払いが必要な道だけでなく、お金をもらえる道（負辺）があるような場合にも使えると覚えておきましょう。
以下で、そもそも負辺がある場合とはどのような場合なのかを説明していきます。
そもそも負辺がある場合とは
負辺とはグラフの辺の重みがマイナスの値を持つことで、特殊なケースになります。
負辺があると最短経路問題は複雑になりますが、ベルマンフォード法を用いることで最短経路を求められるのです。
例えば、ある都市間の移動で支払うお金を最も抑えたい場合、お金を受け取ってしまうと金銭コストは負の値を持ちます。
アルゴリズム上では、このような道があるとルートを見つける計算が複雑になるのです。
ですが、ベルマンフォード法では負辺があってもアルゴリズムとして簡単に処理できるため重宝されます。
ベルマンフォード法とダイクストラ法の違い
ベルマンフォード法とダイクストラ法の違いは辺の重みが負の値があるかないかです。
ダイクストラ法も目的地までの最短ルートを探す方法ですが、負辺がある場合に用いることができません。
ベルマンフォード法だと負の辺が考慮できるだけでなく、負閉路（負辺のサイクル）があった場合に見つけ出せるのです。
負辺を見つけ出せる代わりに、計算量がかかってしまう点は注意しましょう！
ダイクストラ法について詳しく知りたい方は以下の記事をご参照ください。
ベルマンフォード法のアルゴリズム4ステップ
ベルマンフォード法のアルゴリズムは次の手順で行われます。
- 始点以外は距離が無限と仮定
- すべての点から最短距離を調査
- STEP2を(頂点数-1)回行い、最短距離を更新
- (頂点数)回更新されたら、負閉路があると判断
ベルマンフォード法のアルゴリズムは、ダイクストラ法を派生させたようなイメージを持つと分かりやすいでしょう。
それぞれ解説していきます。
STEP1. 始点以外は距離が無限と仮定
まず、始点の距離を0とし、他の全ての頂点の距離を∞として、始点からまだどの頂点へも移動していない状態を表します。
うーん。もう少しかみ砕いて説明して？
つまり、スタート地点の距離は0とし、他の点はスタートからとても遠い「無限大」と考えるのです。
∞と設定するのは、「まだどこも見ていないから距離がわからない」ということを示します。
プログラムとして実行する時にSTEP1は重要ですので、必ず覚えておきましょう。
STEP2. すべての点から最短距離を調査
全ての点を始点として、始点から他の頂点までの距離が、現在記録されている距離よりも短くなるかを確認します。
それぞれの点から最短経路を1回求めるようなものだと考えると理解しやすいでしょう。
もし、イメージが湧きにくいのであれば、負閉路の説明でベルマンフォード法を行っていますので、参考にしてください。
STEP3. STEP2を(頂点数-1)回行い、最短距離を更新
STEP２で行った作業を頂点数-1回行うのが、ベルマンフォード法の大きな特徴です。
もし、負辺がいっぱいあっても、負辺がループしていない（負閉路）でない限り、頂点数-1回で更新が終了することが知られています。
もし、頂点数回目も最短経路が更新されたら、負閉路があると判定できるため、注意しましょう。
STEP4. (頂点数)回更新されたら、負閉路があると判断
全ての道をもう一度チェックして、まだ距離を短くできないかを見ます。
この時点で距離が短くなったら、負閉路がある（いくらでも短くできる）ことを意味していて、最短経路が求められないのです。
そのため、もし更新があった場合は、経路自体を見直してみるようにしましょう。
更新がない場合は、最短経路が求まった証なので、最短経路として確定してしまってOKです。
【補足】負閉路があると最短距離の更新はどうなる？
そもそも、負閉路とは辺の重みの和がマイナスになっている閉路のことです。
負閉路があると最短経路が求められないため、負閉路がありそうな場合はベルマンフォード法を用いることが必要になります。
負閉路があると最短距離の更新はどうなるの？
と気になる方がいると思いますので、実際に例題を用いて説明していきます。
負閉路は下図の例のように総和がマイナスであることが条件です。
左側の例では全ての辺がマイナスで明らかに負閉路ですが、右側の例でも負閉路になることに注意です。
閉路の総和がマイナスなら負閉路になり、最短経路が求められないと考えましょう。
実際に上図の負閉路の左の例で、ベルマンフォード法を行ってみましょう。
ベルマンフォード法の1回目の更新では、A・B・Cそれぞれの点から最短経路が求めています。
そのため、始点であるAもCから辺が出ていることで、更新されていることを押さえておきましょう。
問題は2回目の更新です。
上図のように、すべての頂点が再び更新されてしまいました。
負閉路であることで重みがマイナスに更新されてしまうので、アルゴリズムが永遠に続いてしまうのです。
今回は2回で抑えましたが、負閉路の条件である3回目も更新されることはもう想像できますね。
このように、負閉路があるとベルマンフォード法を正しく実行できないことを押さえておきましょう。
ベルマンフォード法をPythonで実装する方法
ここまで、ベルマンフォード法のアルゴリズムを解説してきました。
ここからはベルマンフォード法のアルゴリズムをPythonコードに落とし込んだ例を紹介します。
以下のコードを実行すると、与えられたグラフにおける各頂点までの最短距離が計算できるので、ぜひ参考にしてください。
import sys
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def bellman_ford(self, src):
# 距離を無限大に初期化
dist = [float("inf")] * self.V
dist[src] = 0
# 最短経路を求める
for _ in range(self.V - 1):
for u, v, w in self.graph:
if dist[u] != float("inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# 負の閉路があるかをチェック
for u, v, w in self.graph:
if dist[u] != float("inf") and dist[u] + w < dist[v]:
print("負の閉路が存在します。")
return
# 最短経路を表示
print("頂点の最短距離:")
for i in range(self.V):
print(f"{i}からの距離: {dist[i]}")
# サンプルグラフの作成
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)
# ベルマンフォード法の実行
src = 0
g.bellman_ford(src)
このコードは、始点から各頂点への最短距離をリストで返し、負の閉路が存在する場合は-1を返すコードです。
g.add_edge(0, 1, -1)は辺を追加していて、(始点, 終点, 重み)のタプルのリストで表現されます。
ベルマンフォード法のアルゴリズムは、すでに解説したように
- 始点以外は距離が無限と仮定
- すべての辺の最短距離を調査
- STEP2を(頂点数-1)回行い、最短距離を更新
- (頂点数)回更新されたら、負閉路があると判断
のように実行されているので、ぜひ確認してみてください。
負閉路がある場合の出力を見たい場合は、以下のグラフに変えてみましょう。
# 負閉路があるグラフ
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, -6)
g.add_edge(4, 3, -3)まとめ
ベルマンフォード法とは重み付きグラフの全頂点における始点からの最短距離を計算するアルゴリズムです。
ダイクストラ法と違い、負辺がある場合にも最短経路が求められるのが特徴になります。
ベルマンフォード法のアルゴリズムは以下の4ステップで行うとよいでしょう。
- 始点以外は距離が無限と仮定
- すべての辺の最短距離を調査
- STEP2を(頂点数-1)回行い、最短距離を更新
- (頂点数)回更新されたら、負閉路があると判断
ベルマンフォード法のPythonでの実装も、アルゴリズムがもとになっています。
なので、アルゴリズムの理解もできるだけ併せて行うようにしましょう！
1度自分で順を追ってみると分かりやすいですよ
あなたはいつもどこかで、
「データサイエンスの勉強がなかなか上手く進まない...」
「勉強しても全体像が見えてこない...」
「本当にデータサイエンティストになれるのかな...」
と不安に感じてはいませんか？
僕も勉強しながら同じような悩みを常に持っていました。
ですが、そんな僕の悩みをまるっと解決してくれたサービスが『スタアカ』です。
データサイエンスを学べるサービスなんて高額なんでしょ？
データサイエンスを学ぶためにもう高額なお金を払う必要はありません。
僕が利用している『スタアカ』のライトプランは月額980円で動画見放題のコスパ最強サブスクです。
「ちょっと興味がある」という方は、受講した感想も載せている記事をご覧ください。
たった月1000円で、もう二度と独学で悩まずに済みます。
正直、「就職・転職までサポートしてほしい」という方にはおすすめできません。
ですが、「勉強の道しるべが欲しい！」「学習を効率的に進めたい」という方にはこの上ないサブスクです。
データサイエンスを学びたい方に最強のサブスク『スタアカ』を気軽に始めてみませんか？
＼月額たった980円！／
講座が毎月追加されるので今後値上がりする可能性大、今が買いどき！
