パス
このパスで変化
調べたエッジ

  • 現在
  • 距離あり
  • 使ったエッジ
  • 経路
  • 負の閉路
ノードのクリックで設定

ベルマン–フォード法についてもっと見る

ベルマン–フォード法

ダイクストラ法は、エッジの長さが負になると破綻します。通行料を取る代わりにお金をくれる道のようなものです。ベルマン–フォード法は破綻しません。何も改善しなくなるまですべてのエッジを何度も調べるだけで、距離が際限なく下がり続ける閉路まで見抜けます。ノードをクリックしてそこから始め、パスを1ステップずつ進めてみましょう。 「再生」で探索を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。エッジはすべて矢印の向きにだけ進める一方向のエッジで、数字はその長さです。長さは負になることもあります。ノードをクリックするとスタートになります。クリックを「ゴール」に切り替えて別のノードをクリックすると、最後にそこへの最短経路が表示されます。各ノードの数字はその時点での距離です。「負の閉路を追加」にチェックを入れると、ベルマン–フォード法が負の閉路を見つける様子を見られます。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. ノードをクリックしてスタートにします。最後に経路を見るには、クリックを「ゴール」に切り替えて別のノードをクリックします。
  2. 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。
  3. 「負の閉路を追加」にチェックを入れると、ベルマン–フォード法が負の閉路を見つける様子を見られます。「新しいグラフ」で別のグラフを試せます。

ベルマン–フォード法のしくみ

スタートの距離を 0、他のノードをすべて無限大にします。そしてパスを繰り返します。各パスで、すべてのエッジ u → v を1回ずつ調べます。u に距離があり、dist(u) にエッジの長さを足した値が dist(v) より短ければ、dist(v) を下げ、そこへの道として u を記録します。パス k の後には、エッジを k 本以下しか使わない最短経路がすべてわかっています。最短経路は各ノードを高々1回しか通らないのでエッジは n − 1 本以下で、n − 1 回のパスで必ず足ります。1回のパスで何も変わらなければ、探索を早めに終えられます。

負の閉路を見つける

閉路のエッジの合計が 0 未満なら、もう一周するたびに経路は必ず短くなるので、最短経路そのものが存在しません。ベルマン–フォード法はこれに気づきます。n − 1 回のパスの後、もう1回のパスでは何も変わらないはずです。まだ緩和できるエッジがあれば、スタートから負の閉路にたどり着けるということで、そのエッジから記録したノードを逆にたどると閉路に入ります。アプリでは、閉路は赤で描かれます。

よくある質問

ベルマン–フォード法とは何ですか?

エッジの長さが負になりうるグラフで、1つのスタートから他のすべてのノードへの最短経路を求めるアルゴリズムです。パスを繰り返してすべてのエッジを緩和し、スタートから負の閉路にたどり着けるならそれを報告します。

ダイクストラ法はなぜ負のエッジで失敗するのですか?

ダイクストラ法は、ノードがキューの中で最も近くなった時点でその距離を確定します。後で見つかった負のエッジが、より短い道でそのノードに戻ってくることがあり、確定した距離が間違いになりえます。ベルマン–フォード法は距離を早めに確定せず、すべてのエッジを調べ続けます。

なぜ n − 1 回のパスなのですか?

最短経路は同じノードを2回通る必要がないので、エッジは n − 1 本以下です。各パスでわかっている最短経路が少なくともエッジ1本分伸びるので、n − 1 回のパスですべて見つかります。

ベルマン–フォード法はどのくらい速いですか?

各パスで E 本のエッジをすべて調べ、パスは最大 V − 1 回なので、計算量は V × E で増えます。これはダイクストラ法より遅いため、ベルマン–フォード法はエッジが負になりうるときに使われます。

グラフはどこかに送信されますか?

いいえ。グラフの作成と探索はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ