K最短路径算法和应用分析.PDF

情报工程 ISSN: 2095-915X TECHNOLOGY INTELLIGENCE ENGINEERING 第1卷 第1期 112-119 2015 年 2 月 ISSN: 2095-915X Vol.1 No.1 112-119 Feb 2015 doi:10.3772/j.issn.2095-915x.2015.01.014 K最短路径算法与应用分析* 付媛，朱礼军，韩红旗 （中国科学技术信息研究所 北京 100038） 摘要：为应对日趋庞大的网络规模和复杂的约束条件给解决 k 最短路径问题带来的挑战，同时给 k 最短 路径在图书情报领域的研究提供建议，对研究现状和算法成果进行总结。首先，介绍 k 最短路径问题的 基本概念。其次，对国内外 k 最短路径问题的算法思想和应用领域研究进展进行梳理，算法思想包括偏 离路径算法、删除路径算法、标号算法、智能算法等，主要的应用领域有交通运输、通信网络、电力系统、 图书情报领域等。最后总结 k 最短路径待解决的问题以及未来研究的方向。 关键词：K 最短路径，偏离路径算法，标号算法 Analysis of K Shortest Paths Algorithms and Applications FU Yuan, ZHU Lijun, HAN Hongqi ( Institute of Scientific and Technical Information of China,Beijing 100038,China ) Abstract: 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. Keywords: K shortest paths problem, deviating from the path algorithm, labeling algorithm 中图分类号：G35；TP301 * 基金项目： 国家自然科学基金资助项目（编号、国家“十二五”科技支撑计划“技术创新服务平台关键技术研 究及应用示范”（编号：2011BAH30B01）、中国科学技术信息研究所预研基金项目“科学合作网络的不连通问题研究”（编号： YY201418）资助。 作者简介：付媛，女，(1989-)，硕士研究生，研究方向：知识工程，E-mail：fuyuan2014@istic.ac.cn。朱礼军，男，(1973-)， 博士，研究员，主要方向：语义网、知识组织系统。韩红旗，男，(1971-)，博士，副研究员，研究方向：文本挖掘、科技情报 分析、科研社会网络 112