赵 见

(中国矿业大学 理学院,江苏 徐州 221116)

求解无环K短路径的Dijkstra算法

赵 见

(中国矿业大学 理学院,江苏 徐州 221116)

对多个标号的求解K短路径的Dijkstra改进算法进行完善,引入两个前驱节点矩阵pre和Kpre,通过这两个矩阵可以求出起始点到当前节点的当前路径,并判断这条路径是否有环,从而在寻找K短路的过程中避免了环的出现,完善后的算法可以求出前K短无环路径,该算法仅需要较少的额外计算量,所以仍然保持了算法的多项式复杂性．然后在不同规模的网络上对完善后的算法进行数值试验,验证了算法的正确性和有效性．

Dijkstra算法;K短路; 无环; 多标号

0 引言

最短路问题是网络分析中的一个经典问题,在实际生活中有着广泛的应用．然而在很多实际情况下,不仅要考虑最短路还要考虑次短路、渐次短路等,即K短路问题[1],它是指在网络图中,对于给定的源点-目标点列出路径长度从最短到第K短的路径,在交通工程、通信等方面具有实际意义．对于最短路问题已经有了比较成熟的算法,最经典的算法是求解非负权网络的最短路问题的Dijkstra算法[2]．对于K短路问题,Eppstein给出了一个算法,对于有向图上的路径允许环的存在[3],Hershberger等人在路径替换的基础上给出了一个新的简单路径的有效算法[4],Ibrahim等人从DNA计算角度考虑这一问题[5],Carlyle等给出接近最短路径的简单路径的K最短路算法[6],Liu等人给出了一个满足多个限制的算法[7],Macgregor考虑了在通信网络中K最短路径问题[8],李成江提出了基……