高速な全点対最短経路アルゴリズム

1. 全点対最短経路問題の計算量の外観

　グラフ $G$ が与えられたときに全点対最短経路(APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと思います. しかしこれらのアルゴリズムは頂点数 $n$ に対して最悪 $O(n^3)$ 時間かかってしまうので, $n=1000$くらいでもちょっと厳しい感じがあります.

　実は辺重み付きグラフのAPSPの計算量には多くの歴史があり、ワーシャルフロイド法以降様々なアルゴリズムが提案されてきました.

APSPのアルゴリズムの歴史

　しかし、任意の $\epsilon>0$ に対して $O(n^{3-\epsilon})$ 時間でAPSPを解くアルゴリズムはこれまで知られていません. なので現在ではそのようなアルゴリズムは存在しないのではないかと予想されています. ちなみにSETHの仮定の下で計算量の下界が示されている問題が多くありますが, APSPのこの下界をSETHの仮定の下で示すのは難しいだろう, という根拠が2016年にCarmosino, Gao, Impagliazzoらによって示されました.

2. 重み無しグラフの全点対最短経路

　以上のことから, 辺重み付きグラフのAPSPを$O(n^{2.99})$で解くのは絶望的であると言えます. では, 辺重み無しグラフのAPSPについてはどうなのでしょうか？以降は「グラフ」は辺重み無しグラフを指すこととします.

　頂点数$n$, 辺数$m$のグラフのAPSPは各頂点から幅優先探索を行うことによって $O(nm)$ 時間で解くことができます. したがってグラフが密で, $m=\Omega(n^2)$ であるならば計算時間は $O(n^3)$ だけかかってしまいます. 

　結論から言うと辺重み無しグラフのAPSPは$m$に依存せず $O(n^{\omega}\log n)$ 時間で解くアルゴリズムが存在します. そのアルゴリズムは[Seidel, 1992]で初めて与えられました. 非常にシンプルなので, 本記事ではこのアルゴリズムについて解説します.

3. Seidel のアルゴリズム

　前提として入力として与えられるグラフ$G$は連結であるとします. したがってその直径は高々$n$です. 更に, 入力において$G$は隣接行列として与えられるとします. そしてアルゴリズムの出力は距離行列$D$とします. ただし$D_{ij}=ij$間の最短経路長と定義します.

　グラフ $G$ に対し, 任意の辺$uv,vw \in E(G)$ に対して 新たな辺$uw$を$G$に追加して得られるグラフを$\tilde{G}$ と定めます. 気持ちとしては$\tilde{G}$ は「全ての長さ2のパスに対してその端点を結ぶ」ことを出来るだけ行って得られるグラフです.

追加した辺を赤く塗っています. 三角形がめちゃくちゃ増えます.

$A$を$G$の隣接行列とします. すると$\tilde{G}$の隣接行列$\tilde{A}$は

になります ($i\neq j$に対し$A^2$の$ij$成分は$ij$間の長さ2のパスの本数を表すからです). したがって, $A^2$を$O(n^{\omega})$時間で計算することで$\tilde{A}$が計算できるので, $\tilde{G}$を得ることが出来ます. 

　この$\tilde{G}$に対して再帰によってAPSPの距離行列$\tilde{D}$を得ます. $\tilde{G}$の直径は$G$の直径の半分くらいになっているので, 再帰を繰り返した結果, 最終的には$G$の直径が$1$(=完全グラフ)となり, この時は(再帰のベーシックケースとして)出力$D$は非対角成分が全て1の行列となります. 更に, 再帰の深さは$\log n$くらいです. というのも$G$の直径が高々$n$で, 一回の再帰で直径が半分くらいになるからです.

　さて, 再帰の出力$\tilde{D}$を使って$G$の距離行列$D$を得ましょう. 下図のように, $\tilde{G}$の$ij$間の最短経路を考えます. 明らかに, 元のグラフ$G$における$ij$間の最短経路長$d_{ij}$が奇数であれば, $\tilde{G}$における$ij$間の最短経路長$\tilde{d}_{ij}$に対して $d_{ij} = 2\tilde{d}_{ij}-1$ が成り立ちます (下図(a)参照. $\tilde{G}$では長さ2のパスを1ホップで通過出来るので, 出来るだけ新しい辺を利用した方が経路長が短くなる). 一方で$\tilde{d}_{ij}$が偶数であれば, $d_{ij}=2\tilde{d}_{ij}$が成り立ちます (下図(b)). 以上より, $d_{ij}$のパリティが分かれば$\tilde{d}_{ij}$を用いて$d_{ij}$を復元できます.

元の最短経路長のパリティが分かれば復元できる.

　ここで, $\tilde{G}$上で ① $ij$間に(a)の図のような最短経路が存在する場合, $d_{ij}=2\tilde{d}_{ij}-1$となります. 一方で ② そのような最短経路が存在しない場合(つまり任意の$ij$間の最短経路が(b)のように赤い辺のみで構成されている場合), $d_{ij}=2\tilde{d}_{ij}$となることに注意します. つまり$d_{ij}$を復元するためには①と②の場合を判別する必要があります.

　そのために行列$X:=\tilde{D}A$を考えます. これは行列積なので$O(n^{\omega})$時間で計算できます. 行列積の定義より$X_{ij}$は

$X_{ij}=\sum_{k=1}^n \tilde{d}_{ik}\cdot A_{kj} = \sum_{k \in N(j)} \tilde{d}_{ik}$

となります. ここで$N(k)$は$G$における$k$の隣接点の集合, $\tilde{d}_{ik}$は$\tilde{G}$における$ik$間の最短経路長です. 

　②を仮定します. すると任意の$k\in N(j)$に対し, $\tilde{d}_{ik} \geq \tilde{d}_{ij}$ が成り立ちます (そうでないとすると, $\tilde{G}$上の$ik$間の最短経路に辺$kj$を足したものが$ij$間の最短経路になりますが, それは②に反するからです. 下図参照).

②で考えるケース. どの$k\in N(j)$も$\tilde{G}$上の$ij$間の最短経路上に含まれていない.

したがって

$\sum_{k \in N(j)} \tilde{d}_{ik} \geq \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

となります. ここで$\mathrm{deg}(j)=|N(j)|$は頂点$j$の$G$における次数です.

　次に①について考えます. この時はある$k\in N(j)$に対して$k$を含むような$\tilde{G}$上の$ij$間最短経路が存在します (下図).

　この$k$に対して $\tilde{d}_{ik} = \tilde{d}_{ij}-1$ が成り立ちます. 更に他の$k'\in N(j)$ に対しても $\tilde{d}_{ik'} \leq \tilde{d}_{ik}+1 = \tilde{d}_{ij}$が成り立ちます ($k$と$k'$間は$\tilde{G}$の辺で繋がっています. 下図参照).

したがって

$\sum_{k \in N(j)} \tilde{d}_{ik} < \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

が成り立ちます.

以上より, 

① $\iff$ $X_{ij}=\sum_{k \in N(j)} \tilde{d}_{ik} < \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

② $\iff$ $X_{ij}=\sum_{k \in N(j)} \tilde{d}_{ik} \geq \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

が成り立つので, 

として$d_{ij}$を求めることが出来ます. これでめでたく出力すべき$D=(d_{ij})$を構成することが出来ました.

　アルゴリズム全体の流れとしては

1. $G$の直径が$1$ならば自明な解を出力.
2. そうでないときは, $A^2$を計算することで$\tilde{A}$を計算し, 再帰に投げることで$\tilde{D}$を得る.
3. $X=\tilde{D}A$を計算し, $X$と$\tilde{D}$を用いて各$ij$に対して$d_{ij}$を計算する.
4. $D=(d_{ij})$を出力.

という感じになります. まず再帰の深さは$O(\log n)$で, ステップ2, 3においては行列積を計算しているので計算時間は$O(n^{\omega})$となり, ステップ4では$O(n^2)$かかるので, 全体の計算時間は$O(n^{\omega}\log n)$となります.

4. まとめ

　辺に重みがある場合と無い場合でAPSPの計算量には大きなギャップがあります. 辺重み付きグラフでは$O(n^{2.99})$では解けなさそうである一方, そうでないグラフに対しては$O(n^{\omega}\log n)=O(n^{2.38})$時間で解くアルゴリズムが知られています. もちろん辺重みが無いスパースなグラフに対しては依然として幅優先探索を用いた$O(nm)$の方が高速ですが, 密な場合はSeidel のアルゴリズムの方が高速であると言えます.
　では, 重み付きグラフに対して$O(n^{2.99})$時間でAPSPを計算するアルゴリズムは存在するのでしょうか？これは$P\neq NP$ほどではないですが, 計算量理論においてかなりホットな話題なので, みなさんもぜひ挑戦してみてください.