A NEW METHOD FINIDNG THE K-TH BEST PATH IN A GRAPH

著者 : H. Ishii (鉄道技研の方！)

雑誌 : Journal of the Operations Research (1978)

a minimum set of ring sum of Euler graphs and an arbitrary path between two vertices is a collection of all paths between the vertices. とあるようにこの考え方を用いている(英弱だからあんまり適切な日本語訳がわかっていない)
Yenのアルゴリズムと同じくらい速い

連結なグラフがあったとして最短路木を考える(最短経路に使われる辺からなる木)
最短路木に含まれない辺をchord、含まれる辺をbranchと呼ぶよ
chordをそれぞれe_1,e_2,...,e_fとするよ(fはm-n+1だよね)
それぞれのe_iに対してC_iってのを考えたい
→chordに含まれる辺をe_iのみ使う、元のグラフの基本サーキットだよ
(僕はグラフ理論弱者なのでわからないですがこのようなサーキットは一意に決まるのでしょうか　決まりそうですけど)
で、P1ってのを最短経路に含まれる辺の集合として
Q1 = P1, R1 = {P1}, E1 = P1 xor Q1(つまり空集合)とするよ
k>=2に対してR_kを以下のように定めるよ
R_k = (R_(k-1)からQ_(k-1)を除いた集合) ∪ {Q_(k-1) xor C_i}
ただし、e_i ∩ E_(k-1) = ∅, Q_(k-1) xor C_i ≠ Q_l (l = 1,...,k-2)
(下から2行目のxorの部分は、元論文だとただの+になってたし、その下の行のk-2の部分はk = 2になってたりとか誤字が多い気がする、k-2のところは実際そうかわからん)
R_kの要素からコストが一番小さい要素を取り出してQ_kとする
んで、E_k = P_1 xor Q_kとするよ
(ここもxorじゃなくて+だった　意味がわからん多分xorだろ)
Q_kがパスだったらk番目のの要素とするよ　違ったらまたR_kを作るステップに戻るよ
K個のパスが得られるまでやる　おわり

完全グラフに対してしか計算量解析してないけど、Yenと同じくらい速いよ〜って書いてた。

前処理でサーキットさえ求めれば後は集合演算だけでKSPを生成できるの端的に言って強い(方法がスマートだよね)

某Zから始まるデータ構造と相性が良さそう……だし、実装も楽そうだし今度実装してみようと思う(けど、誤植っぽいところはどうしようかなぁ、実際手で動かしてみないとわかんないわね)

mits58のメモ