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

摘要

k shonest pathアルゴリズムはネットワーク上での代替経路生成、複数経路を利用することによる負荷分散等への適用が期待される。方向性グラフ上でループレスなk shonest pathを生成するk shonest simple path生成アルゴリズムは、50年間の長きに渡り研究されているが、現状O(knm)の計算量が最小である（nはノード数、mはリンク数）。本稿では、この計算量をO(km(log n+log k））に短縮するアルゴリズム（k-SPF）を提案するとともに、k-SPFアルゴリズムと既存のYenアルゴリズムを実装し、その処理時間を比較する。%k shortest path algorithm is expected to be applied to creating replacement paths and traffic dispersion by using multiple paths on a network, k shortest simple path algorithm, which creates loopless k shortest paths, on the directed graph has been researched as long as 50 years, and its shortest computational complexity so far is O(knm), where n is the number of nodes and m is the number of links. In this paper, our new proposed k shortest simple path algorithm named £-SPF shortens the computational complexity to 0(km (log n + log k)). We also implemented k-SPF and conventional Yen algorithm and compares their processing times.