久々にブログのタイトル通りにアルゴリズム(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$回の反復で(負閉路がない場合の)単一始点最短経路が正しく解けることが保証されます. その正当性として以下の「よくある」証明が知られています.
各$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$を始点とした最短経路長を格納した配列になっています. (証明終)
2. Yen(1970)の方法
Bellman-Ford法の解析では 「各反復では最短経路木に含まれる辺のうち, 少なくとも1本が最短経路として同定されていく」ことを示したわけですが, それでは「各反復では最短経路木に含まれる辺のうち, 少なくとも2本が最短経路として同定されていく」ならば, 反復回数は高々$\lceil n/2\rceil$となります. Yen(1970)による定数倍改善はこの観察に基づきます. Yen(1970)は, 以下のアルゴリズムによって定まる反復に基づくBellman-Ford法の反復回数は高々$\lceil n/2 \rceil$回であることを主張します:
頂点$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$
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.
0 件のコメント:
コメントを投稿