サブロウ丸

主にプログラミングと数学

雰囲気で理解する Yen's algorithm (Find the K shortest paths)

Qiitaに記事を投稿しました。

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