k短路算法.doc

第 K条最短路的算法介绍 1 、前言大家现在已经知道了如何求单源点最短路径问题, 但在实际应用中, 有时候需要除了需要知道最短路径外, 尚需求解次最短路或第三最短路, 即要知道多条最短路, 并排出其长度增加的顺序。如在通信网络中, 有时候某条线路中断, 则需要找一个替代的方案, 这就需要找到几条最短路以备不时之需。这样一类多条最短路问题即称为 K 最短路问题。 2 、二重扫除算法求解第 K 条最短路主要应用的是二重扫除算法( double-sweep algorithm ) ,有些地方也叫双向扫除算法。 概念介绍在介绍这个具体算法之前, 我们要先来看几个概念, 这几个概念在后面具体的算法介绍时需要用到。先看第一个概念,是两类推广运算。?两类运算:推广的求极小值运算与推广的加法运算令R k 表示向量(d 1,d 2,…,d k) 的集合,d i <d j, i=1,2,…, k-1 ; j=2 ,…,k。如( -5, -2,0,6,7)∈R 5 。设 A= (a 1,a 2,…,a k), B= (b 1,b 2,…,b k )是 R k 的两个元素。 Note :R k 中的各个向量的元素必须是①按递增顺序排列;②取不同的数值(除∞之外)。此外,运算的结果 A+B及A×B 也要满足此要求。定义 A与B 的推广的求极小值的运算为: A+B= min k {a i,b i:i=1,2,…, k} ,其中 min k {X} 表示集合 X 中前 k 个最小的元素。定义 A与B 的推广的加法为: A×B= min k {a i+b i:i=1,2,…, k} ,即求出 A与B 的元素分别相加的前 K 个最小的和。 Exp1 :A =( 1,3,4,8)B =( 3,5,7, 16 )则可知: A+B= min 4 {1,3,4,8,3,5,7, 16} =( 1,3,4,5) A×B= min 4 {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) ,确定从源顶点到 j 顶点的 K 最短路径是否可能通过这个相邻顶点,若这样的路存在,则可取新的估计值,并用于进一步的迭代。后向扫除执行类似的算法,其过程是按照顶点号递减的序列(即, j=p, p-1 ,…, 1) ,并且只检查与 j 顶点相邻的后一个顶点(按网络的方向) ,即 i>j 。 算法思想介绍下面我们来看一下双重扫除算法。这个算法的思想其实还是比较简单的, 就是实现起来比较复杂, 要涉及到两种迭代及矩阵运算, 当然还包括前面提及的推广的求极小值运算与推广的加法运算。它的思想是: 从原始点到顶点 j 的第 K 条最短路是由原始点到顶点 i(i是j 的相邻顶点, 最短路从 i 指向 j )的第 K 条最短路加上 i到j 的一段弧。即把与 i 关联的弧作为 K 最短路的最后一段