前K条最短路径算法.doc

[ 注:为了简便我这里只列出算法的步骤和伪代码,详细的数学证明请参见相关论文。 C++ 代码的算法实现可以在我的 e 目录 https:///projects/ksp 下载使用。特别要指出的是葡萄牙教授 Martins 对此算法有深入研究, 发表了为数众多的相关论文, 我这里采用的也是基于他早期提出的 deletion algorithm 。 Martins 的 Fortran 代码可以在这个网站/~eqvm/ 下载,同时这个网站还提供大量相关论文和文献。在此我谨向 Martins 教授致以敬意。]前k 条最短路径算法戴维编译一、算法说明 Deletion Algorithm 删除算法的核心是通过在有向图中已有的最短路径上删除某条弧,并寻找替换的弧来寻找下一条可选的最短路径。删除算法实际上是通过在有向图中增加附加节点和相应的弧来实现的。算法描述如下: Dijkstra 算法求得有向图(N,A) 中以开始节点 s为根的最短路径树(注意,这里的最短路径树并不是最小生成树,因为 Dijkstra 算法并不保证能生成最小生成树),标记从开始节点 s到结束节点 t之间的最短路径为p k, k=1 。 k小于要求的最短路径的最大数目 K,并且仍然有候选路径存在,令当前路径 p=p k,转 3。否则,程序结束。 p中从第一个节点开始的入度大于 1的第一个节点,记为 n h。如果 n h的扩展节点 n ’h不在节点集 N中,则转 4,否则找出路径 p中 n h后面所有节点中,其对应的扩展节点不在 N中的第一个节点,记为n i,转 5。 n h构建一个扩展节点 n ’h,并把其添加到集合 N中,同时从图(N,A) 中所有 n h的前驱节点连接一条到 n ’h的弧,弧对应的权重不变, 添加这些弧到弧集 A中,但 n h在 p中的前一个节点 n h-1除外。计算从开始节点 s到n ’h的最短路径,并记 n i=n h+1 。 p中从 n i开始的所有后续节点,不妨记为 n j,依次执行如下操作: 添加 n j的扩展节点 n ’j到节点集合 N中。 除了路径 p中 n j的前一个节点 n j-1外,分别连接一条从 n j前驱节点到其扩展节点 n ’j的弧,弧上的权值保持不变,并把这些弧添加到弧集 A中。另外,如果 p中 n j的前一个节点 n j-1具有扩展节点 n ’ j-1的话,也需要连接一条从n ’ j-1到n ’j的弧,权值和弧(n j-1,n j)的权值相等。 计算从开始节点 s到 n ’j的最短路径。 ,求得从开始节点 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 多年发展过程中几篇有代表性的论文。] 1. . Azevedo, . Madeira, . Martins and . Pires, A shortest paths ranking algorithm, (1990), Proceedings of the Annual Conference AIRO'90, Models and Me