A NEW METHOD FINIDNG THE K-TH BEST PATH IN A GRAPH
著者 : H. Ishii (鉄道技研の方!)
雑誌 : Journal of the Operations Research (1978)
- 例のごとくK Shortest Pathsに関する論文
- 無向グラフに対するlooplessなKSPを考える
概要
- 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から始まるデータ構造と相性が良さそう……だし、実装も楽そうだし今度実装してみようと思う(けど、誤植っぽいところはどうしようかなぁ、実際手で動かしてみないとわかんないわね)