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