【べるまんふぉーどほう】
ベルマンフォード法 とは？
💡 マイナスの近道があっても迷わない、慎重派の最短ルート探索
📌 このページのポイント
ひよこ ベルマンフォード法って、ダイクストラ法と何が違うの？
ひよこ マイナスの辺って現実にあるのかな？
ペンギン先生 例えば為替レートの計算で、ある通貨を経由すると得をするケースがそれに当たるよ。コストが負になる経路を正しく扱えるのは重要なんだ。
ひよこ どうやって最短距離を求めるの？
ペンギン先生 全ての辺を繰り返しチェックして、もっと短い経路が見つかったら距離を更新する。これをノード数-1回繰り返すと全ノードの最短距離が確定するんだ。
ひよこ 負の閉路を検出できるってすごいね！
ペンギン先生 ノード数-1回の更新が終わった後にもう1回チェックして、まだ距離が短くなるノードがあれば負の閉路が存在するってわかるんだ。計算量はO(VE)で、ダイクストラ法のO(E log V)より遅いけど、この汎用性は大きな武器だよ。
まとめ：ざっくりこれだけ覚えればOK！
「ベルマンフォード法」って出てきたら「負の辺があっても使える最短経路アルゴリズム」と思えればだいたいOK！
📖 おまけ：英語の意味
「Bellman-Ford Algorithm」 ＝ ベルマン・フォードのアルゴリズム
💬 リチャード・ベルマンとレスター・フォードの二人の研究者の名前が由来だよ