図解: Yen's algorithm (Find the K shortest paths)

**K Shortest Path Problem** とは, K番目(ある文脈では1~K番目)に短いパスを見つける問題です. 色々バリエーションがあるみたいですが, 今回は多重有向グラフについて始点と終点を固定した上でK shortest path problelmを解く方法として Yen の アルゴリズムを紹介します[1].

このアルゴリズムは, 負の枝があっても大丈夫ですが, 負のループがあると機能しません.

<br>
さて, そのYenのalgorithmを英語版Wikiのグラフを用いて簡単に説明したいと思います. **始点はC**で**終点はH**とします. 厳密なアルゴリズムではなく, 直感的に理解できようにその流れを説明します. おそらくアルゴリズム自体はそんなに難しくないはずです.


<img src="https://qiita-image-store.s3.amazonaws.com/0/154548/81a244d9-8f7d-843b-028f-c87e4d89ff65.png", width=600>

<br>
まずは第1~K最短路を格納する**配列A**と
第k最短路の候補を格納する**配列B**を用意します. Bには優先度つきキューを用いることで計算量を削減することができます. これからの説明では配列Bはキューとして扱います. <br>
上のグラフの第4最短路まで求めてみましょう.

## 第1最短路
さて, 第1最短路の導出は, Dijkstra法やグラフが負の枝を含む場合はBellman–Ford法を用いて行います.
そしてそれを配列Aに格納します.

![algo_1.png](https://qiita-image-store.s3.amazonaws.com/0/154548/73c7b07c-442f-61b7-19aa-fd00e4deee2a.png)

## 第2最短路

第2最短路ですが, (当たり前ですが)これは第1最短路とは異なるパスであるため
パスの始点から考えたときにどこかのタイミングで第1最短路とは別の道を歩むことになります. (論文中では分岐以降のパスを**deviation**(偏差) **path**と呼んでいます.) パスが分岐する点を**spur node**, 始点からsqur nodeまでを**squr root**と定めます. 以下のようにspur nodeの位置で場合分けを行います.

### spur node が Cの場合
![algo2_1.png](https://qiita-image-store.s3.amazonaws.com/0/154548/58b875ea-093b-b771-50b7-20cc06eb29f4.png)


初っ端から第1最短路とは別の道を歩みます. なので, $C \rightarrow E$ の枝をパスが通ることがないように, 枝の重みを$+\infty$にする, もしくは枝自体を削除します. このとき squr root は $C$です.

![algo2_2.png](https://qiita-image-store.s3.amazonaws.com/0/154548/acacb256-26dc-0a19-ba71-000e1d747acb.png)


そして, spur nodeから終点の$H$までの最短路を求め, それをBに格納します。

![algo2_3.png](https://qiita-image-store.s3.amazonaws.com/0/154548/0264b3b4-e211-b5ff-70ae-bf9d0dd9caa7.png)


### spur node が Eの場合
spur nodeがEの場合も同様に処理します.

![algo2_4.png](https://qiita-image-store.s3.amazonaws.com/0/154548/1d49ea9f-6f94-8ed9-412e-f3a1cda70f7b.png)


$C \rightarrow E$を**spur root**として, $E \rightarrow F$の枝をパスが通れないようにします. そしてEから終点$H$までの最短路を求めて, それとspur rootを合わせて始点から終点までのパスとして, それをBに格納します. この場合は$CFGH$ですね.


![algo2_5.png](https://qiita-image-store.s3.amazonaws.com/0/154548/a8332389-e804-3225-66c0-3fe09ee4d914.png)
![algo2_6.png](https://qiita-image-store.s3.amazonaws.com/0/154548/23382474-6c86-780f-0b85-9b2bafc5ca38.png)


### spur node が Fの場合

同様です.


![algo2_7.png](https://qiita-image-store.s3.amazonaws.com/0/154548/d9c03805-0491-c24f-4fe2-570ca6cb63a5.png)
![algo2_8.png](https://qiita-image-store.s3.amazonaws.com/0/154548/ad51f019-c8a1-d589-581c-716b1b94e65b.png)




### 第2最短路の取り出し
そして, Bに格納されたパスの中から, もっともパス長が短いものを取り出してAに移します. それが**第2最短路**です.

![algo2_9.png](https://qiita-image-store.s3.amazonaws.com/0/154548/9117045c-c6bb-6dcc-8c07-7988692f8e17.png)



## 第3最短路

次は**第2最短路を基準**に, deviation path をBに格納していきます. squr node によって, squr rootが決まりますが, すでに求められている第1~k最短路のなかでsqur rootが含まれているものを探し, squr rootの次の枝の重みを$\infty$, もしくは枝ごと削除します.

### spur node が Cの場合

このとき, squr root は$C$ですが, これは第1最短路に含まれるので, $C \rightarrow E$が通れなくなります. これより最短路を求めると, $CDFH$が求まりますがこれはすでにBに格納されているため, 何もしません.

![algo3_1.png](https://qiita-image-store.s3.amazonaws.com/0/154548/00cff8a0-9415-11df-a200-e1f01d4779d7.png)


### spur node が Eの場合

このとき, squr root は$CE$ですが, これは第1, 2最短路共に含まれるので, $E \rightarrow F$,  $E \rightarrow G$が通れなくなります. 

![algo3_2.png](https://qiita-image-store.s3.amazonaws.com/0/154548/a86b9d79-efd2-529e-4c78-cf5f83d0f083.png)


### spur node が Gの場合

squr root は$CEG$なので, $G \rightarrow H$が通れなくなります. このとき squr nodeから終点までのパスがないため, 何もしません.

![algo3_3.png](https://qiita-image-store.s3.amazonaws.com/0/154548/05f15ece-24d5-37ac-daa5-28c77e0a8885.png)


### 第3最短路の取り出し

![algo3_4.png](https://qiita-image-store.s3.amazonaws.com/0/154548/4f161948-95f6-4c72-e7e5-9bc08d67b392.png)


## 第4最短路

### spur node が Cの場合

![algo4_1.png](https://qiita-image-store.s3.amazonaws.com/0/154548/a0e57a28-0b8e-1efd-cf60-8345d83061a0.png)


### spur node が Dの場合

sour nodeから終点までのパスが存在しないので, 何もしません.

![algo4_2.png](https://qiita-image-store.s3.amazonaws.com/0/154548/23514a42-923e-22be-5e64-39103e9e7e03.png)


### spur node が Fの場合

![algo4_3.png](https://qiita-image-store.s3.amazonaws.com/0/154548/969d955b-1cc2-f40e-a3bf-f258f53fb1ce.png)


### 第4最短路の取り出し

![algo4_4.png](https://qiita-image-store.s3.amazonaws.com/0/154548/c90a481f-12af-aa39-8f74-39923b97fe41.png)



## 計算量

グラフの枝の重みが全て非負の場合, 最短路計算に計算量$O(N^2)$のダイクストラを使えるので全体の計算量は $O(KN^3)$ となります. ただし, Fibonacci heapを使えば計算量が$O(M+N\log N)$ ($M$は枝の本数)になるため, こちらを用いれば全体の計算量は$O(KN(M+N\log N))$です.

グラフの枝に負の重みを持つものが含まれる場合は, 最短路計算に計算量$O(NE)$の Bellman-Ford法を用いるので, 全体の計算量は$O(KN^2E)$です.


## 参考文献
[1] Yen, Jin Y. "Finding the k shortest loopless paths in a network." management Science 17.11 (1971): 712-716.