The Kth Shortest Path Algorithms: Accuracy and Efficiency Evaluation

doi:10.11834/jig.20090832

Views : 0 下载量: 246 CSCD: 0

PDF
Export
Share
Collection
Album

The Kth Shortest Path Algorithms: Accuracy and Efficiency Evaluation
Vol. 14, Issue 8, Pages: 1677(2009)
Published：2009
DOI： 10.11834/jig.20090832
稿件说明：

移动端阅览

DOI：

The Kth Shortest Path Algorithms: Accuracy and Efficiency Evaluation[J]. Journal of Image and Graphics, 2009, 14(8): 1677. DOI： 10.11834/jig.20090832.

摘要

精度和效率是决定最短路径算法实用价值的重要依据。对于K则最短路径问题，各种理论严密算法和有损算法的实用性分析是目前研究的薄弱环节。理论严密算法的实际运行效率比较及其有损算法的精度损耗与效率提高幅度的定量化一直未得到深入研究。针对这一问题，在对K则最短路径算法进行系统分类的基础上，分析了各种经典的理论严密算法和精度有损算法的特征与时间复杂度，结合实际城市路网数据对各种K则最短路径算法的运行效率和精度进行了测试和比较。结果显示，与有损算法相比，理论严密的K则最短路径算法普遍缺乏实用性，只有多重标号算法适合于某些要求精度无损的应用；而一些有损K则最短路径算法以较小的精度损失换取了较大幅度的效率提高，尤以双向搜索算法最具应用推广价值。

Abstract

Efficiency and accuracy are undoubtedly two exclusive indices for shortest path algorithms. The practical analysis on different algorithms solving the Kth shortest path problems has not invoked much research. The comparison on running efficiency between several theoretically rigorous algorithms and the amount of accuracy loss and efficiency improvement brought by lossy Kth shortest path algorithms have remained quantitatively under investigated

and the trade-off between them has not been analyzed in detail. In this paper

with a systematic classification of the most popular Kth shortest path algorithms

the author discussed the characteristics and time complexity of these algorithms

and analyzed and compared their efficiency and accuracy with a real roads network. The author argued that the theoretically rigorous Kth shortest path algorithms

generally lack practical value

only the multi-label setting algorithm can be applied for some applications requiring lossless accuracy. Some lossy Kth shortest path algorithms

greatly improve the efficiency with only little accuracy lost The bidirectional-search algorithm was argued worth paying more attention in practical applications.