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

Analysis of K Shortest Paths Algorithms and Applications

作　　者：付媛[1] 朱礼军[1] 韩红旗[1] FU Yuan ZHU Lijun HAN Hongqi(Institute of Scientific and Technical Information of China,Beijing 100038,China)

机构地区：[1]中国科学技术信息研究所,北京100038

出　　处：《情报工程》2015年第1期112-119,共8页Technology Intelligence Engineering

基　　金：国家自然科学基金资助项目(编号:71473237);国家"十二五"科技支撑计划"技术创新服务平台关键技术研究及应用示范"(编号:2011BAH30B01);中国科学技术信息研究所预研基金项目"科学合作网络的不连通问题研究"(编号:YY201418)资助

摘　　要：为应对日趋庞大的网络规模和复杂的约束条件给解决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.

关 键 词：K最短路径 偏离路径算法 标号算法 

分 类 号：G35[文化科学—情报学] TP301[自动化与计算机技术—计算机系统结构]