前K条最短路径算法

[注：为了简便我这里只列出算法的步骤和伪代码，详细的数学证明请参见相关论文。C++代码的算法实现可以在我的sourceforge目录https://sourceforge.net/projects/ksp下载使用。特别要指出的是葡萄牙教授Martins对此算法有深入研究，发表了为数众多的相关论文，我这里采用的也是基于他早期提出的deletion algorithm。Martins的Fortran代码可以在这个网站http://www.mat.uc.pt/~eqvm/下载，同时这个网站还提供大量相关论文和文献。在此我谨向Martins教授致以敬意。]

前k条最短路径算法

戴维编译

一、算法说明

Deletion Algorithm删除算法的核心是通过在有向图中已有的最短路径上删除某条弧，并寻找替换的弧来寻找下一条可选的最短路径。删除算法实际上是通过在有向图中增加附加节点和相应的弧来实现的。算法描述如下：

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。

4．为节点nh构建一个扩展节点n’h，并把其添加到集合N中，同时从图(N,A)中所有nh的前驱节点连接一条到n’h的弧，弧对应的权重不变，添加这些弧到弧集A中，但nh在p中的前一个节点nh-1除外。计算从开始节点s到n’h的最短路径，并记ni＝nh+1。

5．对于p中从ni开始的所有后续节点，不妨记为nj，依次执行如下操作：

5.1 添加nj的扩展节点n’j到节点集合N中。

5.2 除了路径p中nj的前一个节点nj-1外，分别连接一条从nj前驱节点到其扩展节点n’j的弧，弧上的权值保持不变，并把这些弧添加到弧集A中。另外，如果p中nj的前一个节点nj-1具有扩展节点n’j-1的话，也需要连接一条从n’j-1到n’j的弧，权值和弧(nj-1 , nj)的权值相等。

5.3 计算从开始节点s到n’j的最短路径。

6．更新当前最短路径树，求得从开始节点s到结束节点的当前扩展节点t(k)’之间的最短路径为第k条最短路径，令k=k+1，转2继续。

在上述步骤4、5、6中均需要计算从开始节点到当前扩展节点的最短路径，因为程序开始时便生成了以开始节点为根的最短路径树，那么只要在扩充节点时，记录下每个新节点相对于开始节点的最短路径中其前一个节点编号以及从开始节点到当前节点的最短路径长度，就可以很容易求得任意时刻有向图中从开始节点到结束节点（或其扩充节点）之间的最短路径。

扩展节点：上一条最短路径上的节点可能会在求取下一条最短路径的过程中进行扩展，也就是在上次节点集合的基础上增加相应的新节点，这些新的节点均称为扩展节点，一个扩展节点仍然可能会在求取下一条最短路径的时候进行扩展。表现在示例图中就是在一个节点标记后面加一撇表示是在原始节点上扩展，加两撇表示是在上次扩展节点上再扩展，依次类推。

前驱节点：就是最短路径中某个节点的前一个节点。

二、算法示例

下面以图1所示网络图为例，根据上述算法，分别求得其第k条最短路径，求解过程中有向图的变化情况如图1－5所示，粗体路径表示当前状态下的最短路径，不同类型的圈表示不同阶段生成的节点。

图1 k=1时的最短路径

图2 k=2时的最短路径

图3 k=3时的最短路径

图4 k=4时的最短路径

图5 k=5时的最短路径

参考文献：[这个算法在70年代就提出来了，其间历经完善，发表的论文也是五花八门，为了能让初次接触此算法的人有个系统的认识，我这里列举了这个算法在近10多年发展过程中几篇有代表性的论文。]

1. J.A. Azevedo, J.J.E.R.S. Madeira, E.Q.V. Martins and F.M.A. Pires, A shortest paths ranking algorithm, (1990), Proceedings of the Annual Conference AIRO'90, Models and Methods for Decision Support, Operational Research Society of Italy, 1001-1011.

90这篇论文阐述了基于删除算法(deletion algorithm)的原理及方法，并指出了解决此类问题的三类算法，对其中删除算法以及基于最优化原理(Principle of Optimality)的算法进行了实验比较。

2. E.Q.V. Martins and J.L.E. Santos. A new shortest paths ranking algorithm. Investigacao Operacional, 20:(1):47-62,2000.

Martins在他99年这篇文章中对删除算法进行了改进，提出了MS Algorithm，实际上除了数据结构上的变化外，算法没有做实质性的改动。不过对于要从实现上来优化算法的人来说，当然是值得一看的。

3. E.Q.V. Martins. A new improvement for a k shortest paths algorithm. 2000。（忘了出处了，不好意思）

Martins随后又在他的这篇论文中改进了MS Algorithm，并依次详细列举了对早期的删除算法的逐步改进过程，所以这篇文章也是值得一读的。同样，这次改进也是从数据结构角度来改进算法效率的。

4. Victor M. Jimenez and Andres Marzal. Computing the k shortest paths: A new algorithm and a experimental comparison. 1999. （忘了出处了，不好意思）

终于在这篇文章中有人提出了新的算法--递归枚举算法(REA, Recursive Enumeration Algorithm)。论文中分别对新的算法和Martins的算法MSA以及另外一个叫做Eppstein的人的算法(EA)进行了详细的实验比较。我之所以选择Martins的算法也是因为这篇文章对这些算法的对比实验表明，MSA算法在节点小于2000的情况下表现不错，加之MSA简明易懂并且处在不停的完善中:)。

下面是其他相关的论文，好多哦，不过还是建议你访问Martins教授的网站。