最短経路でも重みの条件が違う
Dijkstra法とBellman–Ford法は、重み付きグラフの始点からの最短距離を扱います。通常のDijkstra法では辺重みがすべて非負であることが重要です。Bellman–Ford法は負の辺を扱えますが、始点から到達できる負の閉路と、その影響を受ける頂点を区別する必要があります。負の辺があることと、負の閉路があることは別です。また、どちらも単に頂点の訪問順を列挙するだけの方法ではなく、辺を使って距離候補を改善する緩和を行います。最短という言葉だけで選ばず、許す重みと求める出力を先に確認してください。
| 観点 | 通常のDijkstra | Bellman–Ford |
|---|---|---|
| 辺の重み | 非負が前提 | 負の辺も扱う |
| 主な処理 | 最小候補を確定 | 全辺の緩和を繰り返す |
| 負の閉路 | 前提の外 | 到達可能性と影響を判定 |
Dijkstraは最小候補を確定する
A→Bが4、A→Cが1、C→Bが2なら、Aの後はCの暫定距離1を選び、Bを4から3へ改善します。非負の辺だけなら、最小の有効な暫定距離を持つ頂点を取り出した時点で、それより短い道が未処理の遠い頂点から後で現れないことを示せます。負の辺が入るとこの根拠が崩れます。例えばA→Bが1、A→Cが2、C→Bが−3なら、Bを1で確定した後に−1となる経路が見つかります。負の閉路がなくても、通常の確定規則をそのまま正当化することはできません。
Bellman–Fordは使う辺数を広げる
Bellman–Ford法は、全辺への緩和を繰り返し、使える辺数を増やした経路を考えます。到達可能な負の閉路がなければ、最短経路は同じ頂点を繰り返さない形へできるので、頂点数Vに対して高々V−1本の辺で足ります。したがってV−1回の走査が基本の上限になります。ただし、配列をその場で更新する実装では、一回の走査中に複数辺分の改善が伝わることがあります。走査回数ごとに「ちょうど何本の経路だけを表すか」を説明する場合は、前回と今回の配列を分けるモデルか、その場更新かを明示します。
負の閉路は影響する範囲を調べる
V−1回の緩和の後にも、始点から到達した距離をさらに改善できる辺があれば、到達可能な負の閉路の影響を示す手掛かりになります。負の閉路を何度も回ることで費用を下げられる頂点には、有限の最小値を返せません。ただし、始点から届かない場所の負の閉路は、その始点の距離へ同じように影響しません。また、到達した負の閉路から進めない別の枝まで、すべて無条件で無限小にするのも誤りです。検出した影響をグラフ上で伝え、どの頂点に有限距離があるか、未到達か、下限がないかを区別して出力します。
時間と早期終了の条件を比較する
隣接リストと適切なヒープを使うDijkstra法は、典型的にO((V+E)log V)などと評価されます。古い候補を残す方式ではキューの大きさも確認します。Bellman–Ford法の標準的な最悪時間はO(VE)ですが、ある走査で一度も改善がなければ終了できる場合があります。Dijkstraで特定のゴールに早期終了するなら、最初に発見した時点ではなく、最小の有効な距離で取り出した時点を使います。数値のオーバーフロー、無限大の表現、到達不能からの加算も実装で検査してください。高速な計画より先に、入力と終了条件が正しさの前提を満たすかを確認します。