新的k最短路算法

被引:15
作者
李成江
机构
[1] 山东科技大学信息与电气工程学院
关键词
动态规划; 最短路径; 无向图;
D O I
暂无
中图分类号
TP301.6 [算法理论];
学科分类号
081202 ;
摘要
在无向图上,对于任意源点—目的点点对,给出了一个新的k最短路算法.这一算法按长度递增给出k最短路路径.算法的复杂度为O(m+nlgn+mlgk).这一算法基于动态规划,首先计算出每一点到源点的最短距离,然后从目的点回溯到源点.根据各点的最短距离信息,给出一棵以目的点为根节点,源点为叶子的树表示的k最短路路径.
引用
收藏
页码:40 / 43
页数:4
相关论文
共 8 条
[1]  
Usi-e K—Shortest Paths Algorithms to Accommodate User Preferences in the Op timization of Pub—lic Transport Travel. WU Qiujin,Hartley J. The 8th International Conference on Applications of Advanced Technologies in Transportation Engineering . 2004
[2]  
A short summary on K shortest path:Algorithms and applications. Myrna Palmgren,Di Yuan. http://www.esc.auckland.ac.nz/Mason/Courses/LinkopingColGen99/kth.pdf . 2006
[3]  
Near-Shortest and K-Shortest Simple Paths. W. Matthew Carlyle,R. Kevin Wood. Networks .
[4]  
Finding thekshortest paths. Eppstein D. SIAM Journal on Computing . 1999
[5]  
A*Prune:An algorithm for findingkshortest paths subject to multiple constraints. G Liu,K G Ramakrishnan. Proceedings of theINFO-COM 2001 Conference . 2001
[6]  
Optimized k-shortest-paths algo-rithm for facility restoration. Macgegor M H,Grover WD. Software Practice and Expe-rience . 1994
[7]  
Finding the k Shortest Simple Paths: A New Algorithm and Its Implementation. John Hershberger,,Matthew Maxel,Subhash Suri. proceedings of the Fifth Workshop on Algorithm Engineering and Experiments (ALENEX 2003) . 2003
[8]  
DNA Implementation of k-shortest Paths Computation. Zuwairie Ibrahim,Yusei Tsuboi,Mohd Saufee Muhammad,et al. 2005 IEEE Congress on Evolutionary Computation[C], Edinburgh, UK . 2005