動的計画法

単一ソース最短路アルゴリズムの代わりに動的計画法を使っても全組最短路問題を解くことができます。\(E = \Theta(V^{2})\) であるような密なグラフに対しては、動的計画法を使ったアプローチの方が Johnson のアルゴリズムよりも単純で (少しだけ) 速いアルゴリズムとなります。 この章ではこれから、入力グラフに負閉路が無いことを仮定します。

まずは動的計画法のアルゴリズムに付き物の再帰方程式を考えます。単一ソースと同様に、"明らかな" 再帰的定義 \[ \mathit{dist}(u, v) = \begin{cases} 0 & \text{if } u = v \\ \min\limits_{x \rightarrow v} (\mathit{dist}(u, x) + w(x \rightarrow v)) & \text{それ以外} \end{cases} \] は入力グラフが DAG であるときにしか正しくありません。有向閉路があると無限ループになってしまうためです。

そこで Bellman-Ford のアルゴリズムと同じように、追加のパラメータを追加してこの無限ループを停止させます。\(\mathit{dist}(u, v, l)\) で \(u\) から \(v\) への辺が \(l\) 個以下の歩道の中で最短のものの長さを表すことにします。任意の二つの頂点の間の最短路は最大でも \(V-1\) 個の辺しか持たないことから、真の最短路の長さは \(\mathit{dist}(u, v, V-1)\) です。単一ソース経路問題に対する Bellman の再帰方程式はこの関数にも適用できます: \[ \mathit{dist}(u, v, l) = \begin{cases} 0 & \text{if } l = 0 \text{ and } u = v \\ \infty & \text{if } l = 0 \text{ and } u \neq v \\ \min \left\lbrace \begin{array}{c} \mathit{dist}(u, v, l-1) \\ \min\limits_{x \rightarrow v} (\mathit{dist}(u, x, l-1) + w(x \rightarrow v)) \end{array} \right\rbrace & \text{ それ以外} \end{cases} \]

この再帰方程式を動的計画法のアルゴリズムに変形するのは簡単です。このアルゴリズムの実行時間は \(\pmb{O(V^{2}E)} = O(V^{4})\) となります。

このアルゴリズムは 1954 年に Alfonso Shimbel (アルフォンソ・シンベル) によって初めて示されました¹。Bellman による Bellman-Ford のアルゴリズムの定式化で見たように、内側の \(l\) と \(v\) に対するループは取り除くことができます。実際に取り除いたアルゴリズムを次に示します:

どのように導出したとしても、最終的に完成するアルゴリズムが \(V\) 個の異なる Bellman-Ford の実行をバラバラに並べたものと全く同じであるというのは驚くに値しません。具体的に言うと、メイン for ループの \(l\) 回目の反復が終わったとき、\(\mathit{dist}[u, v, l]\) は \(u\) から \(v\) への辺を \(l\) 個以下しか使わない路の中で最短のものの長さを表します。

1. Shimbel は入力として距離を表す \(V \times V\) 行列を仮定していたので、彼のオリジナルのアルゴリズムの実行時間はグラフの持つ辺の数に関わらず \(O(V^{4})\) でした。^[return]