練習のための問題は 競技プログラミングの履歴
重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。
計算量は O(|V|·|E|)。
ベルマン–フォード法
詳しい解説
疑似コード
- 今までは頂点(Node)を1つのクラスとしてグラフアルゴリズムのコードを書くことが多かったのですが
- 「辺の緩和を反復」する処理にて辺を線形処理する都合上、辺(Edge)をクラスとして書いたほうがよさそうです
+ | 疑似コード |
- Rubyコードに落とし込む
+ | サンプルコード |
AOJの関連する問題
解答
ポイント
- 実装はWikipediaの疑似コードと以下のサイトを参考にしました
- ワーシャルフロイド法 と同じく、閉路を見つける部分が実装の鬼門です
- 以下の解説がわかりやすかった
始点から到達できる負の閉路がなければ、whileループは最大でも|V| - 1回しか回りません。 逆に考えると、|V|以上ループが回ったら、始点から到達できる負の閉路があるといえます。 ベルマンフォード法を使うと、最短距離の取得と同時に負の閉路の存在を調べる事が出来ます。
+ | 提出コード |
AtCoderの関連する問題
ポイント
- 負の閉路の探索
- ベルマン–フォード法で、探索を実行すると通常は始点から到達可能か否かにかかわらずグラフ内に負閉路が存在すると真が返されます
- → つまり、終点が予め決まっており到達不可能な閉路があったとしたらこの機能は邪魔になる
- → 到達不可能な閉路は無視する実装を行う!