たくさんの単一ソース
全組最短路問題の明らかな解法は、単一ソース最短路問題を各頂点に対して一回ずつ、合計で \(V\) 回解くというものです。具体的に言うと、単一ソース最短路問題を解くたびに一次元の部分配列 \(\mathit{dist}[s, \cdot]\) が埋まります:
procedure \(\texttt{ObviousAPSP}\)(\(V, E, w\))
for 頂点 \(s\) do
\(\mathit{dist}[s, \cdot] \leftarrow \)\(\texttt{SSSP}\)(\(V, E, w, s\))
このアルゴリズムの実行時間が用いる単一ソース最短路アルゴリズムに依存しているのも明らかです。単一ソースのときと同じように、グラフの構造と辺の重みに依存する四種類の選択肢があります:
-
辺に重みが付いていない場合、幅優先探索を使うことで実行時間は \(O(VE) = O(V^{3})\) となる。
-
グラフが非巡回である場合、トポロジカル順序に頂点をスキャンすることで実行時間は \(O(VE) = O(V^{3})\) となる。
-
辺の重みが非負の場合、Dijkstra のアルゴリズムを使うことで実行時間は \(\pmb{O(VE\log V)} = O(V^{3} \log V)\) となる1。
-
以上のどれでもない一般的な場合、Bellman-Ford のアルゴリズムを使うことで実行時間は \(\pmb{O(V^{2}E)} = O(V^{4})\) となる。
-
ここでも、Dijkstra のアルゴリズムの実装で使う二分ヒープをソートされていない配列に入れ替えると、全体の実行時間は (グラフに含まれる辺の数に関係なく) \(O(V^{4})\) となります。また二分ヒープをフィボナッチヒープに入れ替えると、実行時間は \(O(V(E + V\log V)) = \) \(O(VE + V^{2} \log V) = \) \(O(V^{3})\) まで落ちます。[return]