重みの変更

負の辺があると実行が非常に遅くなります: どうにかして削除できないでしょうか？ たくさんの人が思い浮かべる単純なアイデアは、全ての辺の重みを同じだけ増加させることで全ての辺の重みを正にして、Bellman-Ford の代わりに Dijkstra を使うというものです。残念ながら、この単純なアイデアは上手く行きません ――こうすると、多くの辺を持つ路の重みが少ない辺しか持たない路よりも多く増加してしまうからです。次の図に示すように、全ての辺を同じ比率で増加させると、辺をたくさん持つ路は辺を少ししか持たない路よりも速いペースで大きくなります。そのため二つの頂点の間の最短路が変化してしまう可能性があります。

しかしもっと手の込んだ方法を使うと、最短路を保存したまま重みを変更できます。この重みの変更方法の発見者はこの方法を応用した最短路アルゴリズムを 1973 年に示した Donald Johnson (ドナルド・ジョンソン) とされることが多いですが、実は Johnson はこの方法を 1972 年に発表された Jack Edmonds (ジャック・エドモンズ) と Richard Karp (リチャード・カープ) による論文から取ったとしています。また Nobuaki Tomizawa (冨澤 信明) も 1971 年に同じ手法を発表しているほか、Delbert Fulkerson (デルバート・ファルカーソン) による 1961 年の論文でも同じ手法が少し違った形式で示されています。

各頂点 \(v\) に対して、価値 (price) \(\pi (v)\) が割り振られているとします。頂点の価値は正でも負でもゼロでもあり得ます。このとき、新しい重み関数 \(w^{\prime}\) を次のように定義します: \[ w^{\prime}(u \rightarrow v) = \pi(u) + w(u \rightarrow v) - \pi (v) \] 直感的な説明をすると、\(u\) を離れるときには出国税 \(\pi (u)\) を払い、\(v\) に入るときには入国ギフトとして \(\pi(v)\) もらえるということです。

新しい重み関数 \(w^{\prime}\) に対する最短路が最初の重み関数 \(w\) に対する最短路と同じであることを示すのは難しくありません。実際に証明するとこうなります: 任意の路 \(u \rightsquigarrow v \) の全ての中間頂点 \(x\) について、入国ギフトとして \(\pi(x)\) をもらえますが、すぐに \(x\) から出ていくので、このギフトは出国税 \(\pi(x)\) で打ち消されます。したがって \[ w^{\prime}(u \rightsquigarrow v) = \pi(u) + w(u \rightsquigarrow v) - \pi (v) \] が成り立ちます。\(u\) から \(v\) への全ての路の長さが同じ値だけずれるので、\(u\) から \(v\) への最短路は変化しません (違う頂点の組を結ぶ路の長さのずれは異なるので、そのような路同士の長さの上下関係は変わる可能性があります)。