分割統治

1971 年に Michael Fischer (マイケル・フィッシャー) と Albert Meyer (アルバート・マイヤー) によって提案された方法を使うと、さらに格段な高速化が可能です。Bellman の再帰方程式は最短路を少しだけ短い路と一つの辺に分けて考え、目標頂点の全ての前者を考えることで最短路を求めていました。こうする代わりに、最短路をその中間地点にある頂点で分けて二つの路にしてみましょう。こうすると、先ほど定義した \(\mathit{dist}(u, v, l)\) に対する異なる再帰方程式が手に入ります。中間の頂点が存在するのは \(l = 2\) までなので、ベースケースは \(l = 0\) ではなく \(l = 1\) です。また再帰方程式を簡単にするために、全ての頂点 \(v\) に対して \(w (v \rightarrow v) = 0\) と定義しておきます。 \[ \mathit{dist}(u, v, l) = \begin{cases} w(u \rightarrow v) & \text{if } l = 1 \\ \min\limits_{x} (\mathit{dist}(u, x, l/2) + \mathit{dist}(x, v, l/2)) & \text{それ以外} \end{cases} \]

この再帰方程式のままだと \(l\) が \(2\) のべきであるときにしか計算を行うことができず、それ以外の場合には (最大でも) 分数個の辺を持つ最短路を計算することになります。しかしこれは問題ではありません。なぜなら \(\mathit{dist}(u, v, l)\) は 任意の \(l \geq V - 1\) に対して \(u\) から \(v\) の最短路の長さと等しいからです。よって \(l = 2^{\lceil \lg V \rceil} < 2V\) とすれば上手く行きます。

ここでも、動的計画法のアルゴリズムはこの再帰方程式から簡単に手に入ります。実行時間が \(\pmb{O(V^{3} \log V)}\) であることは、アルゴリズムを実際に書かなくても式を見るだけで分かります ――\(u, v, x\) に対して \(V\) 個の値を考え、\(l\) に対しては \(\lg V\) 個の値を考えるからです。次に示す Fischer と Meyer のアルゴリズムの疑似コードでは、\(\mathit{dist}[u,v,i]\) という配列の要素が \(\mathit{dist}(u, v, 2^{i})\) の値を表します。

これまでのアルゴリズムが単一ソース最短路アルゴリズムを \(V\) 回実行するのと同じであったのに対して、このアルゴリズムはそうではありません。つまり、一番内側の処理は辺を緩和しているわけではありません。

Bellman-Ford を初めとするこれまでの動的計画法でそうしてきたように、このアルゴリズムでも配列の最後の次元を取り除くことができ、\(\mathit{dist}[u, v, i]\) の部分を \(\mathit{dist}[u, v]\) とすることで消費空間量を \(O(V^{3})\) から \(O(V^{2})\) に落とせます。この洗練されたアルゴリズムは 1957 年に Leyzorek et al. によって、彼らが Dijkstra のアルゴリズムを示したのと同じ論文で発表されました。