Yenのアルゴリズム

KSPについて少し勉強したので、理解を深めるために実装してみました。
この記事ではアルゴリズムのイメージをつかむことを目的とし、

1. アルゴリズム流れの説明
2. 実装例の紹介

を行います。
厳密な解説を目的としたものではないのでご注意ください。

KSP（K-shortest path problem）とは

ksp（第k最短路問題）とは、読んで字の如く、与えられたグラフ上のある点からある点までの経路の中でk番目に短いものを求める問題を意味します。

その中にもいくつかバリエーションがあり、経路にループを含むかどうかで区別されます。
こちらの記事も参考に！

Yenのアルゴリズム

Yenのアルゴリズムは、その中でもループなし（simple pathともいう）の問題に対するアルゴリズムで、有名なモジュールnetworkxにもshortest_simple_pathsとして実装されています。

辺の重みは全て非負であるという仮定がありますのでご注意を。

アイデア

アルゴリズムのアイデアはとてもシンプルでして、以下のような手順で行われます。

1. 最短路を一つ求める
2. 最短路から派生する経路を総当たりで計算する
3. 計算した経路数が指定の数に到達 or これ以上経路がなくなったら終了

eppsteinのアルゴリズムと同様に、短い経路から派生した経路は短くなる、という思想で作られていることがわかると思います。

二つ目のステップが大事なところなんですが、如何せん文字だけで表現するには限界がありますね。
というわけで、pythonベースの疑似コードを書きました。

擬似コード

ごちゃごちゃ説明するより疑似コードを読んでもらった方がスッキリするかと思います。

list_A : 最終的に第1最短路 ... 第k最短路が入る。最初は空っぽ
list_B : 経路を要素に持つヒープ。距離でソートされていて、経路を列挙する際に経路長が短いものから順に取り出せる
以下アルゴリズム
while True:
    # 手順1
    if list_A is empty:
        sourceからtargetへの最短路を計算する
        それをlist_Bに入れる

    # 手順2
    else:
        for i in range(1, len(prev_path):
            for path in list_A:
                元グラフから点prev_path[k](0 <= k < i)及び辺(prev_path[i-1], prev_path[i])
                を取り除いたグラフ上でprev_path[i]からtargetまでの最短経路を計算する
                得られた経路にprev_path[:i]をくっつけてできる経路を随時list_Bに格納する

    if list_B is not empty:
        list_Bの中で経路長がもっとも短いものをlist_Aに入れ、その経路をprev_pathとする
    else:
        return list_A

• 各経路は[source, node1, node2, ..., target]のような形式で管理されているとします。
• path[i]は経路pathのI番目の点を表します。
• path[: i]は経路pathの先頭からi番目のノードを繋いだ経路を表します。

自分で書いてて少しわかりづらいな、と思ったので少し補足です。

元グラフから点prev_path[k](0 <= k < i)及び辺(prev_path[i-1], prev_path[i])
を取り除いたグラフ上でprev_path[i]からtargetまでの最短経路を計算する

に関してです。
これは同じ経路を何度も計算しないように、ベースとなる経路に含まれる辺、点を少なくとも一つ取り除いた上で最短経路を計算する、という処理になっています。
（元論文では枝の重みを一時的に無限大にするという操作によってこれを実現しています。）

k最短路の候補を管理するのにheapを使っている点も、eppsteinの手法との類似点かなーと思います。まあeppsteinの方が後に出てるのでyenのアルゴリズムの方が先行研究になるんでしょうけども。

実装例

networkxの実装を参考に実装したものをこちらに置いています。

参考

• 元論文
• networkx(ドキュメント)

p.s.
自作コードのプロファイリングをしたところ、双方向ダイクストラ(bidirectional Dijkstra)を使った実装の方が通常のダイクストラを使ったものより二倍近く速くなったもので驚きました。
このスライドで説明されているように、探索領域が大きく削減されることが原因と思われるのですが、興味があるので調べて記事にするかもしれません。