这是本系列的第三篇文章，我将会给大家介绍最后一个新算法，当然这并不是说解决该问题的方法就之有这么一些，然而恰好相反，就在我动笔写本文的几小时前，我又在网上读到了许多非常新的思路，比如有一篇从计算生物学的角度来解决本问题，这自然在我学习能力以外，所以我无法向大家介绍。
好了，言归正传，来看看经我改进的Path Deletion算法（其实改版后完全可以作为自己想到的方法，改个名叫XX算法也行，呵呵）长什么样。
此算法设计的主要动机是来源于对Yen算法的改进（我是这么认为的，继续读下去你就明白了）。从上篇文章我们知道，Yen算法的确“盲目”的在生成很多候选，然后借助优先队列帮助筛选。那么，能否每次从Pk直接生成Pk+1而不需要生成那么多无用的候选呢？答案是肯定的，这就是Path Deletion算法。（接下来我要说的内容将和我之前提出的层次图的概念有非常紧密的联系，如果你对这一概念还不熟悉，强烈建议先阅读我之前那篇讲Dijkstra扩展问题的文章。）
算法的主要思路是DP，而阶段的划分就是层次图中的层。我在次想补充一说明一下层，否则读者将很难明白我想表达的意思。对于第K层，有哪些点是属于它的呢？我们从最短路标号的角度来讲，其实就是每个点的第K小的标号的点。由于图中之有正环，那么不可能存在某点在第K层中的标号是由另一点第K'(K’ > K)中的标号转移而来，换句话说，如果我们把整个层次图中的点拼接到SPT(Shortest Path Tree)中，将会形成一个立体的树状结构，而在这样的SPT中，只有从K层的点指向K'(K’ > K)层中点的边。
再进一步说，这里说的这个立体的SPT其实就是Yen算法中提到的Pseudo Tree（还记得么，我说过它或许还有新特性没被发现），但是换个角度来看，或许就能发现许多新的性质，这又应了看事物的角度不同，得到的结果也不同这句老话。
那么，怎么表示状态和进行状态转移呢？我们用F(x,k)表示x点在第k层中的标号，用Link(x,k)表示这个最优取值的获取是沿着哪条边转移得到的，于是有下面的代码：

[code:cpp]

For each arc headed at x

suppose (y, k’) is the tail of this edge

F(x,k + 1) = min ( F(x,k) , F(y,k’) + cost of this edge)

Link(x, k +1) = The edge which minimize the cost of F(x, k+1)

End for

[/code]

不要慌，我知道你看不懂上面的代码，还有些细节要澄清：

1. 第一层的标号我们采用Dijkstra来计算，因此Link(x,1) = (y,1)，即初始的时候都是层间的转移，y是Dijkstra中转移到x那条最优路上的前驱点;

2. 现在我们手上有一条S -> T的 Pk (k >= 1)路径， 设路径上的点是S = v0, v1, v2, ……,vh = T，那么我们从T开始回溯直到某一点vp( p >0 )，对每一点处理：原来有Link(x, k) = (y,k’)，改为Link(x,k) = (y,k’ + 1);

3. DP代码的计算顺序必须是沿着vp+1,vp+2,……的顺序处理，因为每个点要想DP必须其所有前驱子问题都得到处理。

上面的第二条或许比较奇怪，vp到底是哪一点。为了方便说明，设在算法开始前，任意F(x,k)的标号都是无穷。vp的选取方法为从T向S倒回来前进的路上第一个F(x,k + 1)不为无穷的点（或许(vp, k + 1)同时也在这条路上）。
为什么？其实原始论文中并不是像我这样来处理的，它说的是回溯直到最后一个入度大于零的点为止，然后单独处理这个点。经过我深入分析，发现它这么做不仅麻烦，而且算法复杂度非常高（当然，不排除作者没有在论文中交代明白或是我理解错了），所以这一段我强烈建议有兴趣的读者仔细研究下原文，然后和我的提法作比较。
那么，我这样的处理有什么用？首先，这一算法成功的关键在此，因为它保证了每次DP处理的点数量不超过n个（证明比较巧妙，我是用归纳法做的，读者可以自行思考）。其次，我在回溯时就将求得F(x,k)的那条边调整到了指向F(y,k’ + 1)，这样使状态转移的过程中没有顾虑，没有重复转移。
好了，每次都从上次得到的S -> T路从新DP一次，只要K-1次就可以得到F(T,K)的值，算法的实现非常简单，我写的代码只要Yen算法的一半不到，关键是它拥有非常理想的时间复杂度O(K*|E|)，是一个比较优秀的算法。
但是，该算法也有不足，就是空间消耗是O(K*n)的，而且我也证明了无法用滚动数组的技巧得到更低的复杂度，这的确也是DP一类算法最大的遗憾。

最后，附上原文new_kps.zip ，希望大家研究并与我交流。