Johnson のアルゴリズム
Johnson (ジョンソン) の全組最短路アルゴリズムは全ての辺の重みが非負となるように各頂点に価値 \(\pi(v)\) を割り当て、その後 Dijkstra のアルゴリズムを使って新しい重みに対する最短路を計算します。
まずグラフの全ての頂点に到達できる頂点 \(s\) が存在すると仮定します。Johnson のアルゴリズムは最初 \(s\) から他の全ての頂点に対する最短路を (負辺があっても正しく動く) Bellman-Ford のアルゴリズムを使って計算し、それから価値関数を \(\pi(v) = \mathit{dist}(s, v)\) と定義します。こうした上で、新しい辺の重みを \[ w^{\prime}(u \rightarrow v) = \mathit{dist}(s, u) + w(u \rightarrow v) - \mathit{dist}(s, v) \] と定義します。Bellman-Ford が停止しているので、この新しい辺の重みは非負です！ 辺 \(u \rightarrow v\) が緊張しているとは \(\mathit{dist}(s, u) + w(u \rightarrow v) < \mathit{dist}(s, v)\) が成り立つことであり、単一ソース最短路アルゴリズムは緊張している辺を全て取り除くことを思い出してください (Bellman-Ford が負閉路を検出した場合には最短路が well-defined でないので、Johnson のアルゴリズムはエラーを出して終了します)。
全ての頂点に到達するという条件を満たす頂点 \(s\) が存在しない場合、Bellman-Ford をどこから始めたとしても、いくつかの頂点の価値が無限大になってしまいます。この問題を避けるために、Johnson のアルゴリズムはどんな場合でも最初にまず新しい頂点 \(s\) をグラフに追加して、\(s\) から他の全ての頂点に重さゼロの辺を追加します。このとき他の頂点から \(s\) に戻る辺は追加しません。このように \(s\) を追加すれば \(s\) が中間点となる路は生まれないので、全ての組の間の最短路は変化しません。
Johnson のアルゴリズムの完全な疑似コードを次に示します。アルゴリズムの実行時間は Dijkstra のアルゴリズムの呼び出しによって支配されます。具体的には、\(\textsc{BellmanFord}\) を呼ぶのに \(O(VE)\) 時間かかり、\(\textsc{Dijkstra}\) を \(V\) 回呼ぶのに \(O(VE\log V)\) かかり、他のデータの管理に \(O(V + E)\) 時間かかるので、全体の実行時間は \(\pmb{O(VE \log V)} = O(V^{3} \log V)\)1 となります。結局、負辺があっても遅くなりません！
procedure \(\texttt{JohnsonAPSP}\)(\(V, E, w\))
⟨⟨人工的な頂点を追加する⟩⟩
新しい頂点 \(s\) を追加する
for \(s\) 以外の頂点 \(v\) do
新しい辺 \(s \rightarrow v\) を追加する
\(w(s \rightarrow v) \leftarrow 0\)
⟨⟨頂点の価値を計算する⟩⟩
\(\mathit{dist}[s, \cdot] \leftarrow \)\(\texttt{BellmanFord}\)(\(V, E, w, s\))
if \(\textsc{BellmanFord}\) が負閉路を検出した then
エラーを出す
⟨⟨辺の重みを変更する⟩⟩
for \((u,v) \in E\) do
\(w^{\prime}(u \rightarrow v) \leftarrow \mathit{dist}[s, u] + w(u \rightarrow v) - \mathit{dist}[s, v]\)
⟨⟨重みの変更されたグラフに対する最短路を計算する⟩⟩
for 頂点\(u\) do
\(\mathit{dist}^{\prime}[u, \cdot] \leftarrow \)\(\texttt{Dijkstra}\)(\(V, E, w^{\prime}, u\))
⟨⟨元のグラフに対する最短路を計算する⟩⟩
for 頂点\(u\) do
for 頂点\(v\) do
\(\mathit{dist}[u,v] \leftarrow \mathit{dist}^{\prime}[u, v] - \mathit{dist}[s, u] + \mathit{dist}[s, v]\)
-
...標準的な二分ヒープの実装を使った場合は。一つ前の脚注を参照してください。[return]