緩和の順番を工夫してBellman-Ford法は改善できる

久々にブログのタイトル通りにアルゴリズム(Bellman-Ford法)に関する記事を書きます. それなりに丁寧に書いたつもりなので, Bellman-Ford法を知らない人でも楽しめると思います. プログラムの実行時間はアルゴリズムに加えて実装や実行環境に依存するため, アルゴリズムの計算量では原則として定数倍を無視して議論するわけですが, この記事で紹介する手法はそのような実行環境に依存せず, 本質的に演算回数を定数倍減らしているので競プロ的な(ナイーブな手法を改善していくという)面白さがあると思います.

概要. Bellman-Ford法は$O(mn)$時間で単一始点最短経路問題を解きます. このアルゴリズムは「各辺に対して緩和と呼ばれる操作を行う」ことを$n-1$回繰り返すというアルゴリズムです. 実は緩和を行う辺の順番を工夫することによって反復回数を$n-1$から$n/2$に改善することが可能です [Yen, 1970]. 本稿ではこの単純かつ素晴らしいアイデアを紹介します.

1. Bellman-Ford法とその正当性の証明

フォーマルに書くとBellman-Ford法は以下で定まるアルゴリズムです. まず距離を格納するリスト$\mathrm{dist}[u]$を,

$$\begin{align*} \mathrm{dist}[u] = \begin{cases} 0 & \text{if $s=u$},\\ \infty & \text{otherwise}. \end{cases} \end{align*}$$
で初期化し, その後, 「各辺$e\in E$に対して $\mathrm{relax}(e)$ を行う」を$n-1$回繰り返します. ここで$\mathrm{relax}(e)$とは, 有向辺$e=(u,v)$に対し, その重みを$w_e$とすると,
$$\mathrm{dist}[v] \leftarrow \min\{\mathrm{dist}[v], \mathrm{dist}[u]+w_e\}$$
で更新する操作である.

Bellman-Ford法では見る辺の順番に関しては特に言及されておらず, どのような順番で辺を見たとしても高々$n-1$回の反復で(負閉路がない場合の)単一始点最短経路が正しく解けることが保証されます. その正当性として以下の「よくある」証明が知られています.

「よくある」Bellman-Ford法の証明.

各$i=0,\dots,n-1$に対して, $i$回目の反復が終了した時点での配列$\mathrm{dist}$を$\mathrm{dist}_i$と書くことにします. ただし$\mathrm{dist}_0$は初期化によって得られる$\mathrm{dist}$で, $\mathrm{dist}_{n-1}$はBellman-Ford法の出力です. 次の主張を$i$に関する帰納法で示します: 各$u\in V$に対して$\mathrm{dist}_i[u] = su$-経路のうち辺数が高々$i$であるもののうち最短の長さである. 実際, $i=0$の場合はこの主張は正しいです. また, $i\leq j$まで主張が正しいと仮定すると, $j+1$回目の反復について考えると, 漸化式
$$\begin{align*} \mathrm{dist}_{j+1}[u] = \min_{v \in N^-(u) \cup \{u\}}\{ \mathrm{dist}_j[v] + w_{vu} \} \end{align*}$$
を得ます (ただし$N^-(u)=\{v\in V\colon (v,u)\in E\}$は頂点$u$に入っていく辺のもう一方の端点からなる集合で, $w_{uu}=0$と定義している). 帰納法の仮定より各$\mathrm{dist}_j[v]$は辺数$j$本以下の中での最短$sv$経路の長さなので, $\mathrm{dist}_{j+1}[u]$は所望のものになっており, 主張が証明されました. さて, 元のグラフに負閉路がない場合は$s$から辿り着ける全ての頂点$u$に対して最短$su$経路は辺数が高々$n-1$なので, アルゴリズムの出力$\mathrm{dist}_{n-1}[u]$は確かに頂点$s$を始点とした最短経路長を格納した配列になっています. (証明終)

上記の帰納法に基づく証明により, Bellman-Ford法は始点$s$から近い順に最短経路長を決めていることがわかります. イメージとしては, $s$を根とした最短経路木(最短経路に属する辺からなる木. 最短経路が複数あるときは任意に一つだけ選んでその辺を木に追加していって構成できる) に対して, 根から順番に(幅優先探索の要領で)最短経路長が決定していくことがわかります. 特に, 各反復では最短経路木に含まれる辺のうち, 少なくとも1本が最短経路として同定されていきます. 木の辺数は$n-1$であることからもBellman-Ford法の反復回数が高々$n-1$であることが納得できると思います.

2. Yen(1970)の方法

Bellman-Ford法の解析では 「各反復では最短経路木に含まれる辺のうち, 少なくとも1本が最短経路として同定されていく」ことを示したわけですが, それでは「各反復では最短経路木に含まれる辺のうち, 少なくとも2本が最短経路として同定されていく」ならば, 反復回数は高々$\lceil n/2\rceil$となります. Yen(1970)による定数倍改善はこの観察に基づきます. Yen(1970)は, 以下のアルゴリズムによって定まる反復に基づくBellman-Ford法の反復回数は高々$\lceil n/2 \rceil$回であることを主張します:

1. 頂点に適当に番号づけて, $V=\{v_1,\dots,v_n\}$, 始点を$s=v_1$とする. 各辺$e=(v_i,v_j)$に対し, $i<j$ならば$e$を上昇辺, $i>j$ならば$e$を下降辺と呼ぶ.

2. 頂点を$v_1,\dots,v_n$の順番に見ていき, 各$v_i$に対して$v_i$を始点とする全ての上昇辺に対して緩和を実行する.

3. 頂点を$v_n,\dots,v_1$の順番に見ていき, 各$v_i$に対して$v_i$を始点とする全ての下降辺に対して緩和を実行する.

以下にこのアルゴリズムの正当性の証明を載せます.

Yen(1970)の手法の正当性の証明

頂点$u\in V\setminus \{s\}$を固定し, $su$-最短経路を任意に一つ選び, その経路を頂点列とみなし$P=(w_0,w_1,\dots,w_\ell)$とします (ただし$s=w_0,u=w_\ell$). このパス$P$は上昇辺からなる「増加部分」と下降辺からなる「減少部分」の交互列に分解できます. 例えば$P$が

$v_1 \to v_3 \to v_5 \to v_4 \to v_2 \to v_7 \to v_6$

という頂点列の場合, 

• $v_1 \to v_3 \to v_5$
• $v_5 \to v_4 \to v_2$
• $v_2 \to v_7$
• $v_7 \to v_6$
  

のように, 番号に関する極大な増加列と極大な減少列が交互に現れるように分解できます (始点を$s=v_1$にしているので最初は必ず増加列です). この分解を$P=(U_1,D_1,U_2,D_2)$と表すことにします. ここで$U_1=(v_1,v_3,v_5), U_2 = (v_2,v_7)$は増加列, $D_1=(v_5,v_4,v_2), D_2 = (v_7,v_6)$は減少列です. 一般に増加部分を$U_1,\dots,U_p$, 減少部分を$D_1,\dots,D_q$とし, 連続する上昇列と下降列を繋げて得られる$(U_i,D_i)$という$P$の部分列を山折りと呼ぶことにします. 各山降りは少なくとも2本の辺を含むため, 最短経路$P$が含む山折りの個数は高々$\lceil n/2\rceil$です. Yen(1970)のステップ2では小さい頂点から順番に上昇列を緩和していっているため, $P$の上昇列を順番に同定していきます. 同様にステップ3では$P$の下降列を順番に同定していきます. ステップ2-3を交互に繰り返すため, 一回の反復では一つの山折りに対応する部分列$(U_i,D_i)$の最短経路が順番で同定されていきます. 従って, 山折りの個数, すなわち高々$\lceil n/2\rceil$回の反復で最短経路が求まります. (証明終)

3. その後の進展

[Bannister and Eppstein, 2012]によって, 乱択を用いた反復回数のさらなる定数倍改善$n/3$が得られています (著者のブログ記事). このアルゴリズムも非常に単純なテクニックに基づいたものになっています. 具体的には, Yen(1970)では任意に選ばれた頂点順番に基づいて上昇辺と下降辺が定義されていましたが, これをランダムな順番にすると期待値の意味で反復回数が$n/3$になる, ということを示しています. ここではラフな証明を載せておきます. Yen(1970)の上記の解析により, 任意の最短経路$P$を同定するのに必要な反復回数はそれに含まれる山折りの個数で抑えることができます. 従って, 頂点番号がランダムに振られたときの$P$に含まれる山折りの個数の期待値について考察します. 最短経路の頂点列を$(v_0,\dots,v_\ell)$とし, 各$v_i$はランダムに振られた番号を表すとすると, 山折りの個数の期待値はおおよそ$\ell \cdot \sum_{i=1}^n (1/n) \cdot (i/n)^2 \approx \ell \cdot \int_0^1 x^2 \mathrm{d}x \leq n/3$となります (この式における$(1/n)\cdot (i/n)^2$というのは, パス中の頂点を一つ固定したときにその頂点の番号が$i$になり, かつ両隣の頂点の番号がどちらも$i$以下となる確率を意味します). ざっと論文を目を通したくらいなので詳しいことはわかりませんが, おそらく山折りの個数の集中性を示して(集中不等式の文脈ですでに知られている結果がほぼブラックボックスに使えるっぽい), 終着頂点に関するunion boundをとることによって証明がなされています.

なお, 執筆時(2023年12月時点)では負辺ありの単一始点最短経路問題に対するアルゴリズムのオーダーの改善も知られており, 特にFOCSのbest paperをとったブレイクスルーの結果[Bernstein, Nanongkai, Wulff-Nilsen, 2022]によって, 負辺を含むグラフの単一始点最短経路問題が$O(m\log^8(n)\log W)$時間で解けることが示されました. ここで$W>0$は, $w_e\geq -x$を満たす最小の$x$に対して$W=\max\{2,x\}$で定義される値です. ($2$とのmaxをとっているのはlogをとったときに$0$にならないようにするため.) さらに翌年, [Bringman, Cassis, Fischer, 2023]によって$O(m\log^2(n)\log(nW)\log\log n)$時間アルゴリズムが発表されました.

少し余談になりますが, 同じ会議(FOCS2023)では最短経路に関する別の論文[Duan, Mao, Shu, Yin, FOCS23]もあって, この論文ではcomparison-addition modelと呼ばれるモデルにおいて負辺なしの最短経路問題をダイクストラ法より高速に$O(m\cdot \sqrt{\log n\cdot \log\log n})$時間で解く乱択アルゴリズムを提案しています. comparison-addition modelとは, Bellman-Ford法の緩和操作のように, 数値の加算と比較のみが定数時間で行えるような環境を考えるモデルです. 彼らのアルゴリズムのアイデアは根幹の部分ではダイクストラ法と似たようなことをやっています. 通常のダイクストラ法では全ての頂点をヒープに入れて近い順に頂点を取り出してその周りの辺を緩和するというものでしたが, Duanらのアルゴリズムではパラメータ$k=\sqrt{\log n / \log\log n}$に対して, $n/k$個の頂点をランダムに選び, それらをまずFibnacci heapに入れ, 順番に頂点$u$を取り出して, $u$に"近い"頂点を緩和していくようなことをしています (arXiv版のSection 3参照).

4. 感想

講義のために最小費用流や最短経路問題の色々なアルゴリズムを勉強してみたのですが, マトロイドや離散凸といった一般的な枠組みを追求していく面白さとは違った面白さがあり, シンプルで賢いアルゴリズムは勉強していてとても楽しいですね.

5. 参考文献

• "An algorithm for Finding Shortest Routes from all Source Nodes to a Given Destination in General Network", Jin Y. Yen, Quarterly of Applied Mathematics, 27(4), pp.526--530, 1970.
• "Randomized Speedup of the Bellman–Ford Algorithm", Michael J. Bannister and David Eppstein, Proceedings of ANALCO, 2012.
• "Negative-Weight Single-Source Shortest Paths in Near-linear Time", Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen, Proceedings of FOCS, 2022.
• "Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!", Karl Bringmann, Alejandro Cassis, Nick Fischer, Proceedings of FOCS, 2023.