最短経路の「並べ替えの壁」

向きのあるグラフ$G=(V,E)$で、辺$(u,v)$の長さを$w(u,v)\ge 0$、出発点を$s$、本当の最短距離を$d(v)$とする。アルゴリズムは見積もり$D[v]$を持ち、最初は$D[s]=0$、ほかの頂点は$\infty$とおく。

1. 見積もりを改める操作は、足し算1回と比較1回でできる。これを辺の緩和と呼ぶ。$D[v]$はいつも実際にある道の長さなので、本当の距離を下回らない。

   $$D[v]\leftarrow \min \{D[v],D[u]+w(u,v)\},D[v]\ge d(v)$$

2. ダイクストラ法は、確定した頂点の集合$A$の外で、$D$が最小の頂点$u$を確定する。$A$の頂点ではすでに$D=d$が成り立っているとする。$s$から$u$への道$P$は、どこかで初めて$A$の外へ出る。その辺を$(x,y)$とする。$x$を確定したときに辺を緩和したので$D[y]\le d(x)+w(x,y)$で、$y$から先の辺は負でない。

   $$\ell (P)\ge d(x)+w(x,y)\ge D[y]\ge D[u]$$

3. よって$D[u]=d(u)$で、確定した頂点は二度と直さない。各頂点を1回ずつ取り出し、各辺を1回ずつ緩和すればよい。フィボナッチヒープなら、取り出しは$O(\log n)$、見積もりを下げる操作はならして$O(1)$でできる。

   $$T=O(n\log n+m)$$

4. 取り出す順は、距離の順になる。出発点から$n-1$本の辺が出ているだけの星形グラフなら、距離は辺の長さそのもので、比較は1回も要らない。ところが順番を出すには$n-1$個の長さを並べ替えることになり、比べるだけの方法では次の回数が避けられない（次の章）。

   $${\log }_2(n-1)!\ge \frac{n-1}{2}{\log }_2\frac{n-1}{2}$$

5. ベルマンフォード法は並べ替えをしない。辺の緩和を$k$回くり返すと、辺が$k$本以下の最短経路を持つ頂点は、どれも確定する。手間は$O(mk)$で、$k$が小さければ軽い。

   $$D_k[v]\le \underset{P:s\to v,|P|\le k}{\min }\ell (P)$$

6. 段らは2つを組み合わせた。距離が$b$未満の頂点がすべて確定したとき、見積もりが$b$以上$B$未満の頂点を境目$S$とする。距離が$B$未満でまだ確定していない頂点の最短経路は、どこかで$S$の確定した頂点を通る。そこで$S$からベルマンフォード法を$k$回だけ進め、届いた頂点を$W$とする。$|W|$が$k|S|$を超えたら、境目は届いた頂点の$k$分の1より少ないので、そのまま使う。超えなければ、$W$の中で$k$個以上の頂点を持つ最短経路の木の根だけを、ピボットとして残す。木は重ならないので、ピボットは少ない。

   $$|P|\le \frac{|W|}{k}$$

7. 距離が$B$未満の頂点は、$k$歩のうちに確定したか、最短経路がどこかのピボットを通る。そこでピボットを、束ねて取り出せるデータ構造に入れ、見積もりの小さいほうから$2^{(l-1)t}$個ずつ束にして取り出し、1段下の同じ問題として解く。束の中の順番は決めず、束と残りを分ける値$B_i$だけを求める。段$l$の問題では$|S|\le 2^{lt}$なので、段の数は次で足りる。

   $$\text{段の数}=\lceil \frac{{\log }_{2}n}{t}\rceil$$

8. 主な手間は3つある。1つめはピボットを探す緩和で、1段につき1頂点あたり$O(k)$かかる。2つめはピボットをこのデータ構造に入れる操作で、1回$O(t)$だが、頂点の$k$分の1にしか起きない。3つめは辺から直接入れる操作で、辺ごとに1度、$O(t)$で済む。各頂点を長さ0の辺の輪に置き換え、どの頂点も入る辺と出る辺を2本以下にしておけば、頂点の数は$O(m)$に収まる。

   $$T=O\left(m\left(\frac{k\log n}{t}+\frac{\log n}{k}+t\right)\right)$$

9. $k=\lfloor {\log }^{1/3}n\rfloor$、$t=\lfloor {\log }^{2/3}n\rfloor$とおくと、3つの項はどれも${\log }^{2/3}n$の大きさになる。正しさの証明は段についての帰納法で、このデータ構造にはブロックの連結リストを使う。どちらも論文の第3章にあり、約11ページになる。

   $$T=O\left(m{\log }^{2/3}n\right)$$