K最短路径算法与应用分析

Analysis of K Shortest Paths Algorithms and Applications

为应对日趋庞大的网络规模和复杂的约束条件给解决k最短路径问题带来的挑战,同时给k最短路径在图书情报领域的研究提供建议,对研究现状和算法成果进行总结。首先,介绍k最短路径问题的基本概念。其次,对国内外k最短路径问题的算法思想和应用领域研究进展进行梳理,算法思想包括偏离路径算法、删除路径算法、标号算法、智能算法等,主要的应用领域有交通运输、通信网络、电力系统、图书情报领域等。最后总结k最短路径待解决的问题以及未来研究的方向。

To cope with the challenges of solving the K shortest paths problem by growing of network scale, complicated constraint conditions, and provide suggestions for future research. Firstly, the basic concept of the K shortest paths problem is introduced. Secondly, the research on algorithms and applications at home and abroad to the K shortest paths problem are summarized. Algorithms include deviated path algorithm, route deletion algorithm, labeling algorithm, and intelligent algorithm. Application areas include transportation field, communication networks and word segmentation field. Finally, the paper concludes the K shortest paths problem to be solved and the direction of future study.