計算量最小化を実現するk shortest simple pathアルゴリズム提案

摘要

k shortest pathアルゴリズムはネットワーク上での代替経路生成、複数経路を利用することによる負荷分散等への適用が期待される。方向性グラフ上でループレスなk shottest pathを生成するk shortest simple path生成アルゴリズムは、50年間の長きに渡り研究されているが、現状O（knm）の計算量が最小である（nはノード数、mはリンク数）。本稿では、この計算量をO（km(logn+logk))に短縮するアルゴリズム（k-SPF）を提案するとともに、k-SPF アルゴリズムと既存のYenアルゴリズムを実装し、その処理時間を比較する。