ダイクストラ法よりも高速！66年ぶりの快挙を成し遂げたアルゴリズムについて(1/2)

はじめに

Polaris.AIでお手伝いをさせていただいているSuiginと申します。筆者はアルゴリズムに興味があり、最近最短経路問題について面白い論文が出たので、そちらの解説をさせていただければなと思います。

すこしAIからは離れた内容ですが、お付き合いいただければ幸いです。

この記事の目標

この記事で扱わせていただく論文は以下になります。

R. Duan, J. Mao, X. Mao, X. Shu and L. Yin. "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths". Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 36-44, 2025
リンク(Arxiv): https://arxiv.org/abs/2504.17033

著者による英語の解説はYoutubeにあります。https://youtu.be/LzvvcadKbd0?si=1w6oXRNH1tX4QSd-
また日本語による解説記事も見られるのですが、ここでは論文通りではなく、ダイクストラ法から出発して、どのように改良することができるのかを解説できればなと思います。

記事の流れとしては以下のようになります。
1(今回). 最短経路問題: ここで今までの結果や論文の問題設定を確認します。
2(今回). ダイクストラ法: 記号の導入をしながら、ダイクストラ法を解説します。
3(今回). 分割統治法の適用: 論文の核心のアイデア1つめです。
4(次回). 高速化: 論文の核心のアイデア2つめであるPivot Pruningを紹介します。
5(次回). ダイクストラ法との比較: 論文のタイトルにもなっている"Breaking the Sorting Barrier"がどういう意味かをダイクストラ法と比較しながら解説します。

おまけですが、Suiginによる論文のアルゴリズムの実装は以下にあります。一部ちゃんと実装していない部分もありますが参考にしていただければ光栄です。
https://github.com/Suigin-PolarisAi/BMSSP

1. 最短経路問題 ^[1]

グラフ ^[2]と開始頂点sが与えられたとき、各頂点gについてsからgへの経路のうち重み最小のものを求める問題です。

例えば上のグラフの場合、sからgへ向かう最短経路(=経路のうち重み最小のもの)は重み4,2,4の辺をたどっていくもので、その重みは4+2+4=10になります。g以外の他の頂点についても最短経路の重みを求める必要があることに注意してください。

辺の重みは負である可能性もありますが、以降は全ての辺の重みは非負であるとします。

最短経路の重みが分かれば、実はそこから最短経路自体を求めることも簡単にできるので、例えばカーナビの経路探索や、物流最適化などに応用されることが多いです。

与えられたグラフの頂点の数を$n$、辺の数を$m$としたとき、ダイクストラ法(Dijkstra, 1959)は$O(m + n \log n)$という計算量 ^[3]で最短経路問題を解くことができますが、実はグラフに制約がある場合はこれより高速に解くアルゴリズムがあることが知られていました。例えば以下のようなものがあります。

• 辺の重みが非負整数の場合(Throup, 2004): $O(m+n \log \log \min \{n, C\})$ ($C$は辺の重みの最大値)
• グラフが双方向^[4]の場合(Duan, Mao, Shu, and Yin, 2023): $O(m \sqrt{\log n \log \log n})$

今回紹介するアルゴリズムは、そのような制約がない場合でも、最短経路問題を$O(m (\log n)^{2/3})$で解くことができ、$m$が$n$に比例するような疎なグラフ(辺がそこまで多くないグラフ)の場合はダイクストラ法よりも高速です。また決定的アルゴリズムであり、乱数を使ったアルゴリズムではありません。

2. ダイクストラ法

各頂点$v$の最短距離は$d(v)$であるとします。$d$を求めたいので、ダイクストラ法では現状求まっている経路のうち最小のものの値を$\hat{d}$としてそれを$d$に近づけていきます。そこで$\hat{d}$を最小順に管理するデータ構造を用いると効率的に$d$に近づけられます。実際にアルゴリズムの挙動を確認してみましょう。

さきほど出てきたグラフと同じものですが、$d$はこのようになります。

データ構造を$\mathcal{H}$として、$\mathcal{H}$と$\hat{d}$をこのように初期化します。$\hat{d}$は赤字で示されています。$\mathcal{H}$には$v$と$\hat{d}(v)$の組が$\hat{d}(v)$の最小順で入ります。

まず$\mathcal{H}$の先頭の要素を取り出して、その頂点$u$に注目します(今回は$u$=$s$)。$u$を始点とする辺$(u,v)$を順番に見ていき、$\hat{d}(v) > \hat{d}(u) + w_{uv}$($w_{uv}$は辺の重み)であるなら、$\hat{d}(v)$を$\hat{d}(u) + w_{uv}$ で更新し、$(\hat{d}(v), v)$を$\mathcal{H}$に追加します。

これを繰り返します。次は$c$について見て更新します。ここで頂点$d$への最短距離は6ですが、$\hat{d}(d)=8$になってしまっていることに注意してください。$\mathcal{H}$の要素は緑色で表記していましたが、最短距離と一致しないものは黒字で表すことにします。

次にbを見ることになり、無事頂点dも最短距離に更新されました。

以降は以下のようになります。

これによって最短距離が求まりました。計算量$n$を頂点数、$m$を辺数とすれば、

• 先頭の要素から辺を順番に見ていくパート: アルゴリズムを通して$O(m)$
• $\mathcal{H}$の削除/挿入/更新: 平衡二分探索木にすれば1回につき$O(\log n)$。アルゴリズムを通して$O(n \log n)$

となり合計$O(m+ n \log n)$となります。

ここで平衡二分探索木とはデータを二分木状に管理するデータ構造です。要素が木の左から右へ大きくなるように配置されており、また木の高さ(深さ)が高々$O (\log N)$ ($N$はデータ数)となっているので、大体の操作が1回あたり$O (\log N)$でできます。

3. 分割統治法の適用

ではどのようにすればここから高速化できるでしょうか。$\mathcal{H}$の削除/挿入/更新がボトルネックになっていますが、データ構造の工夫だけでは難しそうです。

ここでデータ構造から頂点を取り出す部分を1つずつではなく、ある決まった数を一気に取り出すことを考えます。ここでの決まった数を$M$と置きます。データ構造で必要になる操作は

• 1個の要素の挿入/更新
• M個の先頭の要素の取り出し

になります。これは以下のように$M$個をまとめてブロックとして持っておく平衡二分探索木によって高速に操作ができるようになります。

実際高さが先ほどの探索木だと3だったのが、いまだと2になっていることが分かると思います。

ブロックが$M$個を超えた場合、ブロックを分割するなどの操作が必要になりますが、1つ目の操作を大体^[5]$O(\log(N/M))$ ($N$はデータ数)、2つ目の操作を$O(M)$、つまり1つの要素あたり$O(1)$になるので、単なる二分平衡木よりも高速に操作ができるようになります。2つの操作をこの計算量でできるデータ構造を$\mathcal{D}$とします。

アルゴリズムも$M$個一気に処理するパートが必要になります。例えば以下の場合で$M=3$だとすると、頂点a,b,dを一気に処理する必要があります。

そのために以下のような条件を満たす関数を考えて、それを分割統治法により実装します。

BMSSP (Bounded Multi-Source Shortest Path)

グラフの頂点数を$n$として$k:=\lfloor (\log n)^{1/3} \rfloor, t:=\lfloor (\log n)^{2/3} \rfloor$とする。
$BMSSP(l, B, S)$は$\hat{d}$を更新しつつ、最終的に$B'$と$U$を出力とする関数で、入力と出力に関して以下のような制約があるとする。

入力($l,B,S$):

• $|S| \leq 2^{lt}$
• 全ての頂点$v\in S$について$B > \hat{d}(v)$
• $v \in S, \hat{d}(v) > d(v)$を満たす頂点への$s$からの最短経路^[6]は$u \in S, \hat{d}(u) = d(u)$を満たす頂点を通る。

出力($B',U$):

• 全ての$u \in U$について$\hat{d}(u)=d(u)$
• $U$は以下の2つを満たす頂点$v$を全て含む。
  • $\hat{d}(v)<B'$
  • sからvへの最短経路は$S$のいずれかの頂点を通る。
• いずれかが成り立つ。
  • $|U|=\Theta (k2^{lt})$でありかつ$B'<B$
  • $B'=B$でありかつ$d(v)<B'$である頂点について

(BMSSP定義終わり)

BMSSPの実装する際に説明しますが、$S$が一気に処理したい頂点集合であり、管理するデータ構造から出てきた$M$個の頂点をそのまま$S$とします。

出力について簡単に言えば$BMSSP(l,B,S)$は最短経路が$S$を通り、重みが$B$未満の頂点を全て出力します。ただし、そのサイズが大きくなりすぎるようだったら($k2^{lt}$のオーダーよりも大きくなりそうだったら)、途中で実行を終了します。

また最短経路問題を解くには$BMSSP(l=\lceil t / \log n \rceil, B=\infty, S=\{s\})$を実行すれば良いです。

BMSSPの実装

先ほどの通り、データ構造$\mathcal{D}$があって、任意の固定されたパラメータ$M$について

• 1個の要素の挿入/更新(insert): $O(\log (N/M))$
• M個の先頭の要素の取り出し(pull): $O(M)$

でできるものが存在します。BMSSPは以下のように$\mathcal{D}$と分割統治法を用いて実装できます。^[7]

BMSSP(l, B, S):
  M=2^{(l-1)t}
  (Dをブロック1つあたりM個で初期化)
  for(v in S): # Sに含まれる各頂点vについて
    D.insert((v, d^(v)))
  U={}
  i=0; B0'=(Sに含まれる頂点vのうちd^(v)の最小値);  
  while(|U|<k2^{lt} && !D.empty()):
    i++
    Si=D.pull()
    Bi=(Dの先頭の頂点の重み。もしDが空なら∞とする)
    Bi', Ui = BMSSP(l-1,Bi,Si)
    (UにUiの要素を追加)
    for((u,v) s.t. u in Ui) { #始点をUiとする辺について
      if(d^(v)>=d^(u)+w(u,v)):
        d^(v)=d^(u)+w(u,v)
          if(d^(v)>=Bi'):
            D.insert(v)
  return min(B,Bi), U

アルゴリズムの挙動をイメージしてみましょう。まず$\mathcal{D}$には$S$の要素が含まれています。緑色の頂点については$\hat{d}(v)=d(v)$(最短距離が求まっている)とし、そうでない頂点は青色で表しています。辺は省略しました。

ここから$M$個取り出した後、$S_i, B_i$は以下のようになります。

$BMSSP(l,B_i,S_i)$を解きます。以下のようになりました。

ここから$U_i$を始点とする辺について重みの更新を行います。更新されたものについては$\mathcal{D}$に足します。いま$\mathcal{D}$に入っている頂点は囲っておきました。

次のループで$S_i, B_i$は以下のようになります。$\mathcal{D}$からすべての要素を取り出したので、$B_i=\infty$となっています。

ここからまた$BMSSP(l, B_i, S_i)$を解いて、$U_i$を始点とする頂点について更新を行います。

$l=0$の場合の挙動が書いていませんが、$M=1$となっており、データ構造から1個ずつ取り出せば良いだけなので、$U$のサイズに気を付けながらダイクストラ法を適用すれば良いです。

BMSSPの計算量

$|U|=O(k2^{lt})$であることから$\mathcal{D}$のサイズも$O(k2^{lt})$であることが示せます。^[8]分割統治法の各階層$l$について、$M=2^{(l-1)t}$なので、1回の挿入は$O(\log (N/M))=O(\log (k2^t))=O(t+\log k)=O((\log n)^{2/3})$です。また各階層で得られる$U_i$は全て排他的であることが言えるので、各階層あたり$O(m+n (\log n)^{2/3})$で計算できます。$l=O((\log n)^{1/3})$層について合計の計算量は$O(m (\log n)^{1/3}+n \log n)$です。

これは残念ながらダイクストラより速くなっておりません。

今回のまとめ

ここまでお付き合いしていただいたのにも関わらず、計算量が改善される所が見せられず申し訳ございません。

ダイクストラから出発して、分割統治法によるアルゴリズムで、データ構造の操作の計算量は削減できましたが、結局全体としてはダイクストラの計算量とまだ同程度です。

ただここから2つ工夫をすると計算量を落とすことができるので、それは機会があれば次回に解説をしたいと思います。そのうち1つが論文の核のアイデアであるPivot Pruningです。

脚注

1. 厳密には単一始点最短経路問題と呼ばれます。

2. 初出のグラフ/計算量理論に関する用語については、このように太字で表記します。詳しくない方には申し訳ございませんが、大まかに意味が通じるように書く努力をします。

3. どのくらい演算を必要かの目安です。$O(n+m)$なら辺と頂点の数に比例する数の演算をする必要があります。

4. ある辺があったとき、反対向きにも同じ重みの辺がある場合。無向グラフとも呼ばれます。対してそのような制約がない場合有向グラフと言います。今回扱うのは有向グラフです。

5. 正しくはならし計算量です。

6. 複数ある可能性がありますが、微小な重みを辺に加えることによって、すべての経路が異なる重みをもつと仮定してもよくなります。論文中のPreliminaryに解説があります。

7. 論文中のAlgorithm 3の簡易バージョンです。

8. 一般のグラフの場合、ここは正しくないですが、実は考えるべきグラフは出次数高々2以下として良いです。論文中のPreliminaryに解説があります。