TechNote

ダイクストラ法を超えた！？ BMSSP解説

公開日: 2025年8月11日 読了時間: 約7分
AI 技術解説 アルゴリズム

本記事では、論文 "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths" で提案された、実数非負重み付き有向グラフにおける単一始点最短経路問題（SSSP）の画期的なアルゴリズムについて、その技術的要点を解説する。

論文要約

本論文は、実数非負重み付き有向グラフにおける単一始点最短経路問題（SSSP）に対し、決定的なO(m log2/3n)時間アルゴリズムを提案する。これは、Fibonacciヒープ等を用いたダイクストラ法のO(m + n log n)という「ソーティング障壁」を、疎なグラフにおいて初めて決定的に破る成果である。

中核概念：階層的探索とピボット選択

このアルゴリズムは、ダイクストラ法の「コスト優先の原則」と、ベルマン・フォード法的な「一斉緩和」の考え方を統合した、分割統治に基づいた階層的な探索戦略をとる。

全体のノードを一度にソートするのではなく、探索のフロンティアから「ピボット」と呼ばれる有望な中継点を効率的に特定し、そこへ探索をジャンプさせることで計算量を削減する。これにより、グローバルなソート処理を回避する。

技術的詳細：主要コンポーネント

FINDPIVOTS 手続き：ピボットの特定

アルゴリズムの最も独創的な部分。フロンティアノード群の中から、計算コストを投下する価値のある「ピボット」を特定する。

FINDPIVOTS の厳密な処理フロー

目的: フロンティアノード u の先に、どれだけ大きな未探索領域が広がっているかを高速に概算する。

処理内容:

  1. フロンティアノード u を一つ選択し、始点とする。
  2. u を起点として、kラウンド限定の集団緩和を実行する。
    • これは「kステップ限定のダイクストラ法」あるいは「kラウンド限定のベルマン・フォード法」と解釈できる。
    • 優先度付きキューからk回ノードを取り出し、隣接エッジを緩和する処理に相当する。
  3. kラウンドの緩和後、u から到達可能になったノードの総数を数える。
  4. この総数が閾値 k を超えた場合、始点となったフロンティアノード u をピボットとして認定する。

注: この処理は最短経路を確定させるものではなく、あくまでグラフの局所的なトポロジー（構造）を調査するための「偵察」である。

BMSSP 手続き：メインループと探索順の決定

アルゴリズム全体の流れを制御する再帰的なメインループ。探索の順番は、単純なコスト順ではなく、より動的な優先度システムによって決定される。

BMSSP における探索順の決定フロー

アルゴリズムは「次に探索すべき頂点」を管理するデータ構造 D を持つ。BMSSP(S) が呼び出された際の処理フローは以下の通り。

  1. 前処理 (Filtering):
    まず P = FINDPIVOTS(S) を実行。引数 S を、より小さいピボット集合 P にフィルタリングする。
  2. 初期化 (Initialization):
    フィルタリング後のピボット集合 P のみをデータ構造 D に格納する。
  3. メインループ (Main Loop):
    D が空になるまで以下のサイクルを繰り返す。
    1. PULL: D から、グローバルに最もコストが低いピボットのグループ Si と、そのコストの下限 Bi を取り出す。
    2. RECURSE: 取り出した Si を対象として、BMSSP(Si, Bi) を再帰的に呼び出す。この呼び出しは、探索の進捗を示す新しいコスト下限 B'i を返す。
    3. UPDATE: 再帰呼び出しの結果を D に反映させる。新たに判明したコスト d を持つ頂点は、以下のルールで挿入される。
      • BATCH PREPEND (高速レーン): コスト d が d ∈ [B'i, Bi) の範囲にある場合。これは「最新の探索で達成された進捗範囲内」を意味し、最優先で処理するため D の先頭に割り込み挿入される。
      • INSERT (通常レーン): コスト d が d ≥ Bi の場合。これは通常のコスト順で D に挿入される。

ダイクストラ法との比較と結論

探索戦略の比較

  • ダイクストラ法: グローバルなコスト最小ノードを1つずつ確定させる、均一な探索。
  • 本手法: グローバルなコスト優先を維持しつつ、局所的なグラフ構造（ピボット）を利用して探索を加速させる、階層的・動的な探索。

性能に関する考察

理論上の最悪計算量では本手法が優れる。しかし、FINDPIVOTS やデータ構造の管理に伴うオーバーヘッドが存在するため、グラフサイズが小さい、あるいは構造が単純な実用的なケースでは、シンプルで定数倍の軽いダイクストラ法の方が高速な場合もあり得る。本手法の真価は、巨大で複雑なグラフにおいて発揮される。

原著論文

本記事で解説した論文は、以下のリンクから閲覧できる。

Duan, R., et al. (2025). Breaking the Sorting Barrier for Directed Single-Source Shortest Paths.