中财网综漫之女主是火影:第K条最短路的算法介绍
来源：百度文库 编辑：中财网 时间：2024/04/29 17:29:49
2010-05-06 21:53
第K条最短路的算法介绍
1、前言
大家现在已经知道了如何求单源点最短路径问题，但在实际应用中，有时候需要除了需要知道最短路径外，尚需求解次最短路或第三最短路，即要知道多条最短路，并排出其长度增加的顺序。如在通信网络中，有时候某条线路中断，则需要找一个替代的方案，这就需要找到几条最短路以备不时之需。这样一类多条最短路问题即称为K最短路问题。
2、二重扫除算法
求解第K条最短路主要应用的是二重扫除算法（double-sweep algorithm），有些地方也叫双向扫除算法。
2.1 概念介绍
在介绍这个具体算法之前，我们要先来看几个概念，这几个概念在后面具体的算法介绍时需要用到。先看第一个概念，是两类推广运算。
? 两类运算：推广的求极小值运算与推广的加法运算
令Rk表示向量（d1，d2，…，dk）的集合，diNote：Rk中的各个向量的元素必须是①按递增顺序排列；②取不同的数值（除∞之外）。此外，运算的结果A＋B及A×B也要满足此要求。
定义A与B的推广的求极小值的运算为：
A＋B＝mink{ai，bi：i＝1，2，…，k}，其中mink{X}表示集合X中前k个最小的元素。
定义A与B的推广的加法为：
A×B＝mink{ai＋bi：i＝1，2，…，k}，即求出A与B的元素分别相加的前K个最小的和。
Exp1：A＝（1，3，4，8）B＝（3，5，7，16）则可知：
A＋B＝min4{1，3，4，8，3，5，7，16}＝（1，3，4，5）
A×B＝min4{1＋3，1＋5，1＋7，1＋16，3＋3，3＋5，…，8＋16}＝{4，6，7，8}
Exp2：A＝（－4，0，7，∞）或B＝（3，4，∞，∞）是可接受的；
而A＝（－4，3，3，9）与B＝（－9，0，∞，9）不可接受。
下面讲一下前向扫除和后向扫除两个概念：
? 前向扫除与后向扫除
双重扫除算法中的每次迭代由两个过程组成：
前向扫除 按照顶点号的递增顺序（即j＝1，2，…，p），通过连续地检查所有与j顶点相邻的前一个顶点i（i后向扫除 执行类似的算法，其过程是按照顶点号递减的序列（即，j＝p，p-1，…，1），并且只检查与j顶点相邻的后一个顶点（按网络的方向），即i>j。
2.2 算法思想介绍
下面我们来看一下双重扫除算法。这个算法的思想其实还是比较简单的，就是实现起来比较复杂，要涉及到两种迭代及矩阵运算，当然还包括前面提及的推广的求极小值运算与推广的加法运算。
它的思想是：从原始点到顶点j的第K条最短路是由原始点到顶点i（i是j的相邻顶点，最短路从i指向j）的第K条最短路加上i到j的一段弧。即把与i关联的弧作为K最短路的最后一段扫视一遍，无论是前向运算或是后向运算，都需要从L或U中取出dij元素参加运算，dij元素在运算中作为K最短路的最后一段弧被挑选，并且以前一次运算的向量为基础，取相应的中间点。
2.3 算法过程
在双重扫除算法过程中，主要反复执行加法和求极小值的运算。
对于每个有向图，我们先对它进行分析，可以用向量 表示从i到j的k条不同最短路的长度。而D0是以 为元素的矩阵。注意，它的元素是 ，这表示这个矩阵中的每个元素都是一个向量，每个向量表示的是从i到j的k条最短路，即是k维向量，如若遇到不足k维的，则以∞补全。如图1，若k为3，则它的D0矩阵可以表示为：
图1
其实从这个矩阵中我们可以看到各个顶点间是否有有向边相连，同时还可以知道该有向边的权值。因为运算中找最短路径，实际上就是计算各条通路的边的权值和再加以比较，从而得到最小值或次小值。
由D0我们可以得到上三角矩阵U和下三角矩阵L如下：
算法的具体思路如下：
⑴ 先设个向量，对原始点到各顶点的最短路长度进行估计。要注意各个值要不小于相应的最优值。除原始点到其本身的最短路用0估计外，其余都可以用∞来估计。即为：
显然， 是个元素值为向量的向量。其中向量 表示从i到j的k条最短的不同路的长度。
如图1中，令d10＝（（0，∞，∞），（∞，∞，∞），（∞，∞，∞），（∞，∞，∞））
⑵ 然后根据原来的估计值，可以根据前向和后向扫除计算出新的估计值：
后向扫除：d1(2r+1)＝d1(2r+1)L＋d1(2r)
前向扫除：d1(2r+2)＝d1(2r+2)U＋d1(2r＋1) （r＝0，1，2，…）
其中矩阵运算中的加法和乘法分别指前面提及的推广的求极小值和推广的加法运算。令 ，可将后向扫除公式分解为：
由上式可见在求 时， 本身也参与了运算，但是，观察L，我们可知L的最后一列元素全为 ，由于 ，而 ，所以 ；而求 时，只需知道 ，不需知道其它几项；由此一步步往前推，我们可以将整个 完整地计算出来，因此称其为后向扫除。如下，是 向量中的各个元素的计算式：
即
……
同理：我们可以将前向扫除的计算公式进行分解，如下：
在计算 时也要用到 其本身，但根据U的特点，我们可以发现先可以计算出 ，然后可以依次计算出 ， ，……，这与上面的后向扫除类似，只是这里我们要先从前面开始计算，因此称其为前向扫除。具体的 的各个元素的计算式与上面后向扫除类似，这里就不一一写出了。
如图1，可计算d141＝（∞，∞，∞），d131＝（∞，∞，∞），
d121＝（∞，∞，∞），d111＝（0，∞，∞）；（后向）
（前向）d112＝（0，∞，∞），
d122＝（∞，∞，∞）+（0，∞，∞）×（2，∞，∞）＝（2，∞，∞）
d132＝（∞，∞，∞）+（0，∞，∞）×（5，∞，∞）＝（5，∞，∞）
d142＝（∞，∞，∞）+（2，∞，∞）×（3，∞，∞）
+（5，∞，∞）×（3，∞，∞）＝（5，8，∞）；
（后向）d143＝（5，8，∞），
d133＝（5，∞，∞）
d123＝（2，∞，∞）+（5，∞，∞）×（2，∞，∞）＝（2，7，∞）
d112＝（0，∞，∞）；
（前向）d113＝（0，∞，∞），
d123＝（2，7，∞）+（0，∞，∞）×（2，∞，∞）＝（2，7，∞）
d133＝（5，∞，∞）+（0，∞，∞）×（5，∞，∞）＝（5，∞，∞）
d143＝（5，8，∞）+（2，7，∞）×（3，∞，∞）
+（5，∞，∞）×（3，∞，∞）＝（5，8，10）；
（后向）d144＝（5，8，10），
d134＝（5，∞，∞）
d124＝（2，7，∞）+（5，∞，∞）×（2，∞，∞）＝（2，7，∞）
d114＝（0，∞，∞）；
显然，第三第四次迭代后，运算结果相同，从而可得：
d1＝（（0，∞，∞），（2，7，∞），（5，∞，∞），（5，8，10））
⑶ 当 与 的每个分量都相等时，算法中止。
2.4 路径的确定
K最短路长度求得以后，我们要确定相应的路径，这时我们可以采用追踪的方法。设需要知道从源顶点到i顶点的第m最短路长的路径，我们可以令 为该路的路长，并且令j表示与i相邻的顶点，则
这里 是弧ji的长度， 是对应与顶点j的t最短路长度，t≤m。
第K条最短路的算法介绍
1、前言
大家现在已经知道了如何求单源点最短路径问题，但在实际应用中，有时候需要除了需要知道最短路径外，尚需求解次最短路或第三最短路，即要知道多条最短路，并排出其长度增加的顺序。如在通信网络中，有时候某条线路中断，则需要找一个替代的方案，这就需要找到几条最短路以备不时之需。这样一类多条最短路问题即称为K最短路问题。
2、二重扫除算法
求解第K条最短路主要应用的是二重扫除算法（double-sweep algorithm），有些地方也叫双向扫除算法。
2.1 概念介绍
在介绍这个具体算法之前，我们要先来看几个概念，这几个概念在后面具体的算法介绍时需要用到。先看第一个概念，是两类推广运算。
? 两类运算：推广的求极小值运算与推广的加法运算
令Rk表示向量（d1，d2，…，dk）的集合，di
定义A与B的推广的求极小值的运算为：
A＋B＝mink{ai，bi：i＝1，2，…，k}，其中mink{X}表示集合X中前k个最小的元素。
定义A与B的推广的加法为：
A×B＝mink{ai＋bi：i＝1，2，…，k}，即求出A与B的元素分别相加的前K个最小的和。
Exp1：A＝（1，3，4，8）B＝（3，5，7，16）则可知：
A＋B＝min4{1，3，4，8，3，5，7，16}＝（1，3，4，5）
A×B＝min4{1＋3，1＋5，1＋7，1＋16，3＋3，3＋5，…，8＋16}＝{4，6，7，8}
Exp2：A＝（－4，0，7，∞）或B＝（3，4，∞，∞）是可接受的；
而A＝（－4，3，3，9）与B＝（－9，0，∞，9）不可接受。
下面讲一下前向扫除和后向扫除两个概念：
? 前向扫除与后向扫除
双重扫除算法中的每次迭代由两个过程组成：
前向扫除 按照顶点号的递增顺序（即j＝1，2，…，p），通过连续地检查所有与j顶点相邻的前一个顶点i（i
2.2 算法思想介绍
下面我们来看一下双重扫除算法。这个算法的思想其实还是比较简单的，就是实现起来比较复杂，要涉及到两种迭代及矩阵运算，当然还包括前面提及的推广的求极小值运算与推广的加法运算。
它的思想是：从原始点到顶点j的第K条最短路是由原始点到顶点i（i是j的相邻顶点，最短路从i指向j）的第K条最短路加上i到j的一段弧。即把与i关联的弧作为K最短路的最后一段扫视一遍，无论是前向运算或是后向运算，都需要从L或U中取出dij元素参加运算，dij元素在运算中作为K最短路的最后一段弧被挑选，并且以前一次运算的向量为基础，取相应的中间点。
2.3 算法过程
在双重扫除算法过程中，主要反复执行加法和求极小值的运算。
对于每个有向图，我们先对它进行分析，可以用向量 表示从i到j的k条不同最短路的长度。而D0是以 为元素的矩阵。注意，它的元素是 ，这表示这个矩阵中的每个元素都是一个向量，每个向量表示的是从i到j的k条最短路，即是k维向量，如若遇到不足k维的，则以∞补全。如图1，若k为3，则它的D0矩阵可以表示为：
图1
其实从这个矩阵中我们可以看到各个顶点间是否有有向边相连，同时还可以知道该有向边的权值。因为运算中找最短路径，实际上就是计算各条通路的边的权值和再加以比较，从而得到最小值或次小值。
由D0我们可以得到上三角矩阵U和下三角矩阵L如下：
算法的具体思路如下：
⑴ 先设个向量，对原始点到各顶点的最短路长度进行估计。要注意各个值要不小于相应的最优值。除原始点到其本身的最短路用0估计外，其余都可以用∞来估计。即为：
显然， 是个元素值为向量的向量。其中向量 表示从i到j的k条最短的不同路的长度。
如图1中，令d10＝（（0，∞，∞），（∞，∞，∞），（∞，∞，∞），（∞，∞，∞））
⑵ 然后根据原来的估计值，可以根据前向和后向扫除计算出新的估计值：
后向扫除：d1(2r+1)＝d1(2r+1)L＋d1(2r)
前向扫除：d1(2r+2)＝d1(2r+2)U＋d1(2r＋1) （r＝0，1，2，…）
其中矩阵运算中的加法和乘法分别指前面提及的推广的求极小值和推广的加法运算。令 ，可将后向扫除公式分解为：
由上式可见在求 时， 本身也参与了运算，但是，观察L，我们可知L的最后一列元素全为 ，由于 ，而 ，所以 ；而求 时，只需知道 ，不需知道其它几项；由此一步步往前推，我们可以将整个 完整地计算出来，因此称其为后向扫除。如下，是 向量中的各个元素的计算式：
即
……
同理：我们可以将前向扫除的计算公式进行分解，如下：
在计算 时也要用到 其本身，但根据U的特点，我们可以发现先可以计算出 ，然后可以依次计算出 ， ，……，这与上面的后向扫除类似，只是这里我们要先从前面开始计算，因此称其为前向扫除。具体的 的各个元素的计算式与上面后向扫除类似，这里就不一一写出了。
如图1，可计算d141＝（∞，∞，∞），d131＝（∞，∞，∞），
d121＝（∞，∞，∞），d111＝（0，∞，∞）；（后向）
（前向）d112＝（0，∞，∞），
d122＝（∞，∞，∞）+（0，∞，∞）×（2，∞，∞）＝（2，∞，∞）
d132＝（∞，∞，∞）+（0，∞，∞）×（5，∞，∞）＝（5，∞，∞）
d142＝（∞，∞，∞）+（2，∞，∞）×（3，∞，∞）
+（5，∞，∞）×（3，∞，∞）＝（5，8，∞）；
（后向）d143＝（5，8，∞），
d133＝（5，∞，∞）
d123＝（2，∞，∞）+（5，∞，∞）×（2，∞，∞）＝（2，7，∞）
d112＝（0，∞，∞）；
（前向）d113＝（0，∞，∞），
d123＝（2，7，∞）+（0，∞，∞）×（2，∞，∞）＝（2，7，∞）
d133＝（5，∞，∞）+（0，∞，∞）×（5，∞，∞）＝（5，∞，∞）
d143＝（5，8，∞）+（2，7，∞）×（3，∞，∞）
+（5，∞，∞）×（3，∞，∞）＝（5，8，10）；
（后向）d144＝（5，8，10），
d134＝（5，∞，∞）
d124＝（2，7，∞）+（5，∞，∞）×（2，∞，∞）＝（2，7，∞）
d114＝（0，∞，∞）；
显然，第三第四次迭代后，运算结果相同，从而可得：
d1＝（（0，∞，∞），（2，7，∞），（5，∞，∞），（5，8，10））
⑶ 当 与 的每个分量都相等时，算法中止。
2.4 路径的确定
K最短路长度求得以后，我们要确定相应的路径，这时我们可以采用追踪的方法。设需要知道从源顶点到i顶点的第m最短路长的路径，我们可以令 为该路的路长，并且令j表示与i相邻的顶点，则
这里 是弧ji的长度， 是对应与顶点j的t最短路长度，t≤m。
关于图的最短路算法
什么是最短路由算法？
哪位大侠知道最短路由算法的程序
谁知道最短路由算法程序 {语言 C++均可}
求k阶斐波那契序列的第m项的值f 算法
怎么编程实现求图最短路的Dijkstra算法
南昌到奉化市的最短路线图
K-均值聚类算法的流程图
谁有红黑数算法的详细介绍
唱K小鱼仙中有多少条人鱼?请分别把她们的介绍给我.谢谢
世界上最怪的算法
求一个算法把n个数中的第k大的数求出来，要求时间复杂度为O（n）
图论的混合图如何求最短路
k条最短路径算法
k近邻算法
人体第45条染色体缺失最严重的后果是什么目前医学上能治好吗
谁有DFS 的算法介绍???
美国证券市场的144K条列
K线图的5条线是什么意思？
请教20元1000条短信的算法
最精确的电能计量算法是哪种？
除湿量最简单的算法是什么？
三星显示器的短路
蓄电池的微短路..