問題: 無向グラフ$G=(V, E)$と$V$の部分集合$S$ (special node)が与えられる。$S$上の任意の2点間の距離で最短のものを求めよ。
方針: すべてのspecial nodeから各点への最短距離を調べるために$K$回ダイクストラする。この際、距離のテーブルは毎回使いまわしてよくて、枝刈りができる。また、special nodeを調べる順番をシャッフルすれば期待計算量が保証できる。
正当性について。今、special node $A_1, ..., A_{i-1}$について二頂点間の最短距離の最小値が求まっているとし、距離のテーブル$d$が$d[v] := v$と$A_1, ..., A_{i-1}$との最短距離の最小値、という状態になっているとする。ここからさらにspecial node $A_i$を始点にダイクストラするとする。この際、頂点$u$から$v$を更新しようとした時に$d[u] + w(u, v) \ge d[v]$であれば、$v$は無視してよい。なぜなら$A_i$から任意の頂点$x$に到達する際の最短経路が$v$を通るとしても、それ以下の距離で$A_1, ..., A_{i-1}$のいずれかから$x$に到達できることになるからだ。
計算量について。$K$回ダイクストラをしている間に頂点$v$がキューからポップされる回数の期待値を考える。$v$がキューからポップされるのは、今調べているspecial nodeと$v$の最短距離が以前調べたすべてのspecial nodeと$v$の最短距離より小さい場合である。したがって、この期待値は$K$個のspecial nodeと$v$との最短距離を$d_1, ..., d_K$とした時、$(d_i)$をシャッフルした列のLDSの長さの期待値に等しく、${O}(\sqrt K)$らしい[1]。したがって、ポップに関する期待計算量は${O}(\sqrt KN \log N)$となる。また、ポップした頂点の隣接頂点を調べてdecrease keyする操作の期待計算量は、二分ヒープなら${O}(\sqrt KM \log N)$となる。 したがって、全体の期待計算量は${O}(\sqrt K (M+N)\log N)$ということになる。
waterfallsさんの別の乱択の方針も面白かった。special nodeをランダムに2分割して、一方を始点としたダイクストラをすると、最短距離を与える二頂点が異なるグループに属している時に正しい答えが出る。そうなる確率は1/2なので、何回もやって最小値を取ればよい。このテクニックは無向グラフの最短閉路アルゴリズムで見たことがある: http://research.haifa.ac.il/~raphy/papers/all-cycles.pdf
この評価については https://www.math.ucdavis.edu/~romik/book/ のp.9に簡潔な証明が載っている。ランダム順列のLISの長さの期待値に関する研究はJ. M. Hammersley, A few seedlings of researchが初出らしい。（後者は読んでいない） ↩︎
