たくさんの単一ソース

全組最短路問題の明らかな解法は、単一ソース最短路問題を各頂点に対して一回ずつ、合計で \(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\))

このアルゴリズムの実行時間が用いる単一ソース最短路アルゴリズムに依存しているのも明らかです。単一ソースのときと同じように、グラフの構造と辺の重みに依存する四種類の選択肢があります:


  1. ここでも、Dijkstra のアルゴリズムの実装で使う二分ヒープをソートされていない配列に入れ替えると、全体の実行時間は (グラフに含まれる辺の数に関係なく) \(O(V^{4})\) となります。また二分ヒープをフィボナッチヒープに入れ替えると、実行時間は \(O(V(E + V\log V)) = \) \(O(VE + V^{2} \log V) = \) \(O(V^{3})\) まで落ちます。[return]

広告