EppsteinのK-shortest pathを求めるアルゴリズムを実装したので解説します。

本記事の目的は、Eppsteinのアルゴリズムをふんわりと理解することです。詳細に理解したい方は元論文も合わせてご覧ください。

K-shortest path problem とは

k-shortest path problemとは、k番目に短い経路を求める問題で、いくつかのバリエーションがあります。

1. ループなし
   求める経路にループ（閉路）を含まない
2. ループあり
   求める経路にループがあっても良い

一般的に、ループなしの問題を解く方が難しい問題で、より計算時間がかかるようになっています。
Yenのアルゴリズムが有名です。

今回紹介するEppsteinのアルゴリズムはループありの問題に対するアルゴリズムです。

Eppsteinのアルゴリズムについて

各辺の重みが非負値をとるような有向グラフにおける1-K最短路(巡回あり)を求めるアルゴリズムです。
より効率よく計算できる、Lazy Eppsteinというものもあるようです。気が向いたら記事にします。

記号の準備

$$ \begin{align}&G = (V,E) :\text{ 各辺の重みが非負値をとる有向グラフ}\\
&T :\text{ Gの逆最短路木}\\
&s, t \in V: \text{始点、終点}\\
&l(e), \forall e\in E: \text{枝の長さ}\\
&d(u,v),\forall u,v\in V:\text{s-t間の(最短)距離}
\end{align}$$

アルゴリズムの大まかな流れ

1. $G$の逆グラフ上で$t$を始点とする最短路木を構成
2. $\forall e\in E$に対して*ポテンシャルを計算
3. $T$上の点を始点に持つような全ての辺を*ポテンシャルによって二分ヒープにする
4. 3で作った2-ヒープを結合して3-ヒープとパスグラフ(各ノードがパスを表現)を作成
   パスグラフもヒープ構造(4-ヒープ)で、親の方が子よりもコストが小さくなっている
5. パスグラフ上を最良優先探索(or Frederickson)によって探索し、K最短路を求める

このアルゴリズムによって得られた経路は、$(最短路木に乗ってる部分)\rightarrow (Sidetrack)\rightarrow\dots\rightarrow(終点)$という形をしている。

ポテンシャル・・・$\delta(e)=l(e)-d(e.\text{from}, t)-d(e.\text{to}, t)\geq0 \forall e\in E$
で定義され、最短路からどれだけ離れているかを表す。
n-ヒープ・・・子(各ノードの出次数)が高々n個のヒープ

計算量

逆最短路木$T$の構成に優先度付きキューを使ったダイクストラ法を利用することで$O(|E|log|V|)=O(|V|log|V|)$
パスグラフの作成に$O(|E|+|V|log|V|)$
K最短路の探索に$O(KlogK)$もしくは$O(K)$

以上をまとめると、$O(K+|E|+|V|log|V|)$で計算することができます。

印象的だったポイント

• 枝の重みをポテンシャルに変換
  どの枝を優先的に選べばいいか効率的に決めることができている
• パスを1: 最短経路を通る部分と2: それ以外の部分に分割して考える
  こういう分割を行うことでヒープを使った効率良い探索が可能になっている

その他感想

• パスグラフの構成が肝(実装も難しい)
• 個人的にハッとするようなアイデアだったのでとても興味深い論文だった。
• 最短路木の構成に双方向ダイクストラ法を使ってみたらもう少し速く計算できるケースがありそう。

実装

Python実装をこちらのリポジトリに置いてます。
依存ライブラリはnumpyとnetworkxです。
出力は一応経路長の昇順になっているのでおそらくきちんと動いていると思います。

もしバグや間違いなどありましたら気軽にご連絡ください。