トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

ベルマン–フォード法

[アルゴリズム,グラフアルゴリズム]

練習のための問題は 競技プログラミングの履歴

重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。

計算量は O(|V|·|E|)

ベルマン–フォード法

  詳しい解説

疑似コード

  • 今までは頂点(Node)を1つのクラスとしてグラフアルゴリズムのコードを書くことが多かったのですが
  • 「辺の緩和を反復」する処理にて辺を線形処理する都合上、辺(Edge)をクラスとして書いたほうがよさそうです

+ 疑似コード

  • Rubyコードに落とし込む

+ サンプルコード

  AOJの関連する問題

解答

ポイント

 始点から到達できる負の閉路がなければ、whileループは最大でも|V| - 1回しか回りません。
 逆に考えると、|V|以上ループが回ったら、始点から到達できる負の閉路があるといえます。
 ベルマンフォード法を使うと、最短距離の取得と同時に負の閉路の存在を調べる事が出来ます。

+ 提出コード

  AtCoderの関連する問題

ポイント

  • 負の閉路の探索
    • ベルマン–フォード法で、探索を実行すると通常は始点から到達可能か否かにかかわらずグラフ内に負閉路が存在すると真が返されます
    • → つまり、終点が予め決まっており到達不可能な閉路があったとしたらこの機能は邪魔になる
    • → 到達不可能な閉路は無視する実装を行う!
お名前: コメント: