前K条最短路径算法.doc

前 k 条最短路径算法戴维编译一、算法说明 DeletionAlgorithm 删除算法的核心是通过在有向图中已有的最短路径上删除某条弧,并寻找替换的弧来寻找下一条可选的最短路径。删除算法实际上是通过在有向图中增加附加节点和相应的弧来实现的。算法描述如下: 1. 利用 Dijkstra 算法求得有向图 (N,A) 中以开始节点 s 为根的最短路径树(注意,这里的最短路径树并不是最小生成树,因为 Dijkstra 算法并不保证能生成最小生成树),标记从开始节点 s 到结束节点 t 之间的最短路径为 pk , k=1 。2. 如果 k小于要求的最短路径的最大数目K,并且仍然有候选路径存在, 令当前路径 p=pk ,转3。否则,程序结束。3. 找出当前路径 p 中从第一个节点开始的入度大于 1 的第一个节点,记为 nh 。如果 nh 的扩展节点 n’ h 不在节点集 N 中,则转 4 ,否则找出路径 p 中 nh 后面所有节点中,其对应的扩展节点不在 N 中的第一个节点,记为 ni ,转 5 。 nh 构建一个扩展节点 n’ h ,并把其添加到集合 N 中,同时从图 (N,A) 中所有 nh 的前驱节点 连接一条到 n’ h 的弧,弧对应的权重不变,添加这些弧到弧集 A 中,但 nh 在 p 中的前一个节点 nh-1 除外。计算从开始节点 s 到 n’ h 的最短路径,并记 ni = nh+1 。5. 对于 p 中从 ni 开始的所有后续节点,不妨记为 nj ,依次执行如下操作: 添加 nj 的扩展节点 n’ j 到节点集合 N 中。 除了路径 p 中 nj 的前一个节点 nj-1 外,分别连接一条从 nj 前驱节点到其扩展节点 n’ j 的弧,弧上的权值保持不变,并把这些弧添加到弧集 A 中。另外,如果 p 中 nj 的前一个节点 nj-1 具有扩展节点 n’ j-1 的话,也需要连接一条从 n’ j-1 到 n’ j 的弧,权值和弧 (nj-1 ,nj ) 的权值相等。 计算从开始节点 s 到 n’ j 的最短路径。6. 更新当前最短路径树,求得从开始节点 s 到结束节点的当前扩展节点 t(k)’ 之间的最短路径为第k 条最短路径,令 k=k+1 ,转 2 继续。 在上述步骤 4 、 5 、 6 中均需要计算从开始节点到当前扩展节点的最短路径,因为程序开始时便生成了以开始节点为根的最短路径树,那么只要在扩充节点时,记录下每个新节点相对于开始节点的最短路径中其前一个节点编号以及从开始节点到当前节点的最短路径长度,就可以很容易求得任意时刻有向图中从开始节点到结束节点(或其扩充节点)之间的最短路径。          扩展节点 :上一条最短路径上的节点可能会在求取下一条最短路径的过程中进行扩展 ,也就是在上次节点集合的基础上增加相应的新节点,这些新的节点均称为扩展节点,其会继承被扩展结点的邻接边关系(具体请参见上述步骤4,5)。一个扩展节点仍然可能会在求取下一条最短路径的时候进行扩展,表现在示例图中就是在一个节点标记后面加一撇表示是在原始节点上扩展,加两撇表示是在上次扩展节点上再扩展,依次类推。        前驱节点 :就是最短路径中某个节点的前一个节点。 二、算法示例  下面以图 1 所示网络图为例,根据上述算法,分别求得其第 k 条最短路径,求解过程中有向图的变化情况如图 1 - 5 所示,粗体路径表示当前状态下的最短路径,不同类型的圈表示不同阶段生成的节点 。    图1 k=1时的最短路径  图2 k=2时的最短路径 图3 k=3时的最短路径 图4 k=4时的最短路径 图5 k=5时的最短路径        参考文献:[这个算法在70年代就提出来了,其间历经完善,发表的论文也是五花八门,为了能让初次接触此算法的人有个系统的认识,我这里列举了这个算法在近10多年发展过程中几篇有代表性的论文。],,,Ashortestpathsrankingalgorithm,(1990),ProceedingsoftheAnnualConferenceAIRO'90,ModelsandMethodsforDecisionSupport,OperationalResearchSocietyofItaly,1001-(deletionalgorithm)的原理及方法,并指出了解决此类问题的三类算法,对其中删除算法以及基于最优化原理(PrincipleofOptimality)的算法进行了实验比较。