中文摘要：

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

英文摘要：

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.