带单一限制条件的单源多权最短路径问题

带单一限制条件的单源多权最短路径问题

2000年，冯德民和谢娟英提出了一种基于单一限制条件的最短路径算法（以下简称冯算法）。带单一限制条件的单源多权最短路径问题(以下简称此类问题)在实际中比比皆是,解决此类问题算法有着非常广泛的应用价值。遗憾的是,冯算法不是一个正确的算法。本文中首先分析了冯算法的不足之处,并给出冯算法的一个反例;然后,本文提出了一个解决此类问题的算法(以下简称本算法),并证明本算法是正确的。本算法中设计了独特的数据结构并且用十分简单的方法解决了此类问题,这是本算法的一个显著特点。1边性质、vn、wj、li定义1设有向图G=(V(G),E(G)),其中V(G)={vi|1≤i≤n,n为图中顶点数},称V(G)为图G的顶点集;E(G)={epq|epq=〈vp,vq〉,〈vp,vq〉为一条边,vp,vq∈V(G),1≤p,q≤n},称E(G)为图G的有向边集,w1(p,q),w2(p,q),…,wh(p,q)是图G的一条边〈vp,vq〉上的h个权,wi(p,q)≥0(i=1,2,…,h);称v1为源点,vn为终点。定义2对应定义1中的h个权,有h个数k1,k2,…,kh(0≤kj≤1,1≤j≤h;且它们称为评价系数;一条边〈vp,vq〉的评价长度为函数的值(函数val(p,q)称为评价函数);一条路径上各条j=1边的评价长度和称为此条路径评价长度。定义3设一个顶点序列v1,…,vn是从v1到vn的一条路径,若该路径上所有边上的一个权wj(本文中规定wj为w1)之和满足∑wj≤LI,其中LI为一给定的正常数,则称这一路径为满足对权wj限制的路径。定义4设l1,l2,…,lm分别是从v1到vn的满足对权wj限制的所有m条路径,则称这m条路径中评价长度最小的那条路径为满足对权wj限制的最短路径。2冯算法的不足和反例2.1lenth+val,n冯算法的存储结构、主要变量说明和算法请见文献中。设val(k,k-1)为<vk,vk-1>这条边上评价长度,w1(k-1,k)为这条边上权w1的值,设nlen=dist[k-1].LENTH+val(k,k-1),nsw=disk[k-1].SW+w1(k-1,k);冯算法的基本思路是:当从某个顶点vk-1出发,遍历其邻接顶点vk时,如果下列条件成立(冯算法中p为总的限制值,在本文中用LI表示冯算法中的p常量)。则用以下赋值语句进行“替换”,即:冯算法的不足之处是:当上述条件(1)成立,但同时nsw>dist[k].SW也成立时,按照冯算法要进行上述“替换”,这样,dist[k].LENTH值比“替换”前小,但dist[k].SW值却比“替换”前大,结果常常找不出一个正确的解来。2.2邻接点逻辑的计算例1一个有向图如图1所示。其中v1是源点,v4是终点,LI=8,两个评价系数为:k1=k2=0.5,评价函数为:val(p,q)=0.5×(w1(p,q)+w2(p,q))。按照冯算法,从v1出发分别遍历v3、v2、v4得:dist.LENTH=3,dist.SW=3;dist.LENTH=7.5,dist.SW=5;dist.LENTH=20,dist.SW=7,再从v3出发遍历其邻接点v2。因为:(nsw=dist.SW+4=7<LI=8)且(nlen=dist.LENTH+0.5(4+1)=5.5<dist.LENTH=7.5)这一条件成立,按照冯算法要进行如下“替换”;dist.LENTH=5.5,dist.SW=7,再从v2出发遍历v4终点,因为此时dist.SW+2=9>LI=8,所以用冯算法只找到一个满足限制条件LI=8的解,为dist.LENTH=20;但实际上还存在一个解,即<v1,v2,v4>,此条路径的∑w1=5+2=7<LI,而评价长度值为0.5×(5+10+2+2)=9.5。3该算法为了简便,以下规定:受限制的权为w1,定义中h=2,即:只有两个权w1,w2;多权的情况用本算法求解是完全类似的。3.1顶小状态spd的大小比较定义5图中一个顶点vp的一个状态(state)。从源点v1出发经过一条路径到达一个顶点vp,该路径上各条边上的权w1之和以及评价长度之和分别记为∑w1,∑val;则称(∑val,∑w1)这个二元组为顶点vp的一个状态。显然,vp可能有多个状态,顶点vp的第d个状态记为Spd,即:Spd=(vapd,w1pd)。定义6两个状态间按“字典序”进行的大小比较。设一个状态为Spd=(vapd,w1pd),另一状态为Smj=(vamj,w1mj),(m和p可为相同的值),如果(vapd<vamj或((vapd=vamj)且(w1pd<w1mj))),则称Spd<Smj,即:状态Spd按字典序比状态Smj“小”;如果(vapd=vamj且w1pd=w1mj),则称Spd=Smj,即:两状态值相等。按上面定义的字典序,我们可以从多个状态中找出一个最小状态。3.2状态结论的生成图G是一个有n个顶点的有向图,它的邻接表由n个单链表(称为邻接单链表)和一维数组hg组成;第p(1≤p≤n)个邻接单链表中每个结点(称为邻接结点)有4个域,如下所示:〈vp,vq〉(1≤q≤n)为图G中一条边,wpq、valpq分别是这条边上权w1的值和评价长度的值,link是指针域,指向此单链表的下一个结点。本算法中,同一个邻接单链表中各个结点按wpq域的值非递减的顺序在邻接单链表中按照从前(表头结点)往后(表尾结点)的顺序依次排列,这样做可提高整个算法的效率。hg[p]中存的是第p个邻接单链表的头指针。(2)状态表状态表由一维数组hs和n个称为状态单链表的单链表组成。根据定义5,一个顶点可能有多个状态,本文中为每个顶点vp(1≤p≤n)建立了一个状态单链表(此状态单链表也称为vp的状态单链表),一个状态单链表中的一个结点称为一个状态结点,一个顶点vp的状态结点共有6个域。如下所示:其中vall,ww中分别存的是如定义5中定义的vp一个状态(vapd,w1pd)的二个分量值vapd和w1pd。(vall,ww)也称为此状态结点的状态。act/sta:称为活动/静止域;当act/sta域值为0时,此状态结点称为(定义为)一个活动结点,当act/sta域值为1时,此状态结点称为(定义为)一个静止结点。ver称为顶点域,一个顶点vp的状态结点的ver域的值即为vp本身(为了简化,ver域中仅写上vp的下标p)。pre:称为直接前趋域。一个状态结点(设为D结点)的pre域中存状态表中另一个状态结点(设为C结点)的地址值,C结点的状态必须是D结点状态的前趋状态(见下面定义7)。slink为指针域,指向下一个状态结点。定义7前趋状态、后继状态从一个顶点vp(此时它的状态为Spd=(vapd,w1pd))出发访问它的一邻接点vq,<vp,vq>为一条边,vq的一个状态为Sqg=(vaqg,w1qg),如果下述等式成立:则称,Spd为Sqg的前趋状态,Sqg为Spd的后继状态。从定义7可知,因为val(p,q)≥0且w1(p,q)≥0,显然有下面的引理1成立。引理1后继状态大于或等于前趋状态(字典序)求最短路径常要求求出这条最短路径本身(即:通过哪些顶点)。起初,本算法是在状态结点中使用一些标号域以便记住一条最短路径上各个顶点,但使用标号域的算法相当繁琐;后来,经过反复研究,本算法借用了C语言的一个特点可用指针变量存储一个结点的地址,本算法在状态结点中不用标号域而是改用前面所说的ver和pre域,其中pre域是一个指针变量,它指着状态表中一个具有前趋状态的结点,这样确定一条最短路径所通过的各个顶点非常的方便、快捷(只需从终点的一个状态结点出发通过pre域连续地找具有前趋状态的结点,并同时打印相应状态结点的顶点域的值,直到找到一个状态结点其pre域的值为空(即:∧)时为止。因为一条最短路径上最多有n个顶点,所以打印一条最短路径最多需时间为O(n))。在状态结点中设置pre域来存储具有前趋状态的结点的地址是本算法的一个显著特点。头数组hs中每个元素有两个域,如右所示:hs[r].lk(1≤r≤n)中存的状态表中顶点vr的状态单链表的头指针,hs[r].alk中存的是hs[r].lk所指向的状态单链表中排在最前面的第一个活动结点的地址值。定义8一个状态单链表中的状态结点是按字典序排列的。如果一个状态单链表中原来有任两个状态结点SE、SF,SE的状态为(ve,ww1e),SF的状态为(vf,ww1f),它们都经过下面(1)、(2)两个步骤处理后,这个状态单链表就称为是按字典序排列的。(1)如果(ve≤vf且ww1e≤ww1f),则将SF结点从此状态单链表中删除。即:留“小”(SE)丢“大”(SF)。(2)如果(ve≤vf且ww1e≥ww1f)成立(注:如果出现ve=vf且ww1e=ww1f情况仍按(1)处理,即:删除SE或SF),则SE这个结点是SF这个结点的前趋结点。本文中状态单链表均按字典序排列。定义9将一个状态结点按字典序插入状态单链表。这种插入是指插入后此状态单链表仍是按字典序排列的。3.3在最短路径kv1为源点,vn为终点;限制条件为LI。(1)仅以w1(p,q)作为每条边〈vp,vq〉上的长度,用Dijktra算法求出在这种情况下从v1到vn的最短距离LT1n,如果LT1n>LI,则无解,算法结束。(2)置初值。依次扫描邻接表中以hg为头指针的邻接单链表中各个邻接结点(设当前扫描结点为E结点),如果E.wpq域的值>LI,则停止扫描,转(3);否则,每扫描到一个E结点则在状态表中产生并插入一个状态结点(设此结点为F结点),F结点的地址存在hs[q].alk和hs[q].lk中,而且F结点的6个域赋值如下:F.act/sta=0(即此状态结点开始时为活动结点),F.vall=E.valpq,F.ww=E.wpq,F.ver=E.q,F.pre=∧,F.slink=∧。(3)在状态表中找出按字典序最小的活动状态将hs[r].alk(1≤r≤n)所指的n个状态单链表中的排在最前面的第一个活动结点状态进行字典序大小的比较,找出一个最小状态(mval,mww1)和具有此状态的状态结点U(设指向此结点的指针为hs[u].alk)(1≤u≤n),如果u=n(vn为终点。),则找到了一满足限制条件的最短路径,其评价长度值为mval,此条最短路径通过哪些顶点可通过如在3.2节中状态表一节中描述那样借助pre和ver域快速求得,然后结束此算法。如果u≠n,则将U.act/sta域置为1,然后将hs[u].alk指向U后的第一个活动结点,设U结点的地址为AU。(4)从本算法第(3)步中刚找出的U结点的U.ver(它是图中一个顶点vu)出发遍历其所有邻接点vy(通过访问邻接表中以hg[u]为头指针的邻接单链表来实现遍历);设此时vu的状态值为(mval,mww1),如果mww1+w1(u,y)>LI,则停止遍历,转(3);否则,产生一个vy的状态,即:(mval+val(u,y),mww1+w1(u,y)),并产生一个状态结点Y,设其地址为AY,设mvuy=mval+val(u,y),mw1uy=mww1+w(u,y),则Y结点如下所示:然后将此结点按字典序插入状态表中以hs[y].alk为头指针的单链表中,转(3)。3.4状态结论sn.守护神从本算法可知:以hs[n].alk为头指针的状态单链表中第一个被找出的状态结点,即是本算法要找出的最后一个状态结点;如果一个状态结点U,它是所求的最短路径的终点vn所在状态结点,它必须满足下面3个等式:(3)、(4)、(5)。(下面用符号→表示所指向的结点,用符号→.state表示所指向的结点的状态。)下面来证明vn的所有状态结点(记为SN,即:SN.ver等于vn)中的状态(记为SN.state)均有SN.state≥U.state成立即可。SN.state分二种情况:(1)SN已求出。那么SN在以hs[n].alk为头指针的状态单链表中,因为U结点为此状态单链表的头结点(因为:U=hs[n].alk→),且状态单链表又按字典序排列,所以,SN.state≥U.state。(2)SN未求出,SN的状态是现在状态表中一个活动结点(记为SAN)的状态的一个后继状态(即:SN.state=SAN的后继状态)。从引理1知:SAN的后继状态≥SAN.state,SN.state=SAN的后继状态≥SAN.state,从U结点满足的3个等式可看出,U结点是当前状态表中所有活动结点中字典序最小的结点,所以:SAN.state≥U.state,SN.state≥SAN.state≥U.state,SN.state≥U.state。从上面(1)、(2)可知:SN.state≥U.state。3.5种方法解决不太复杂的问题文献将带限制条件的此类最短路径问题列为NP问题;也就是说,本算法时间复杂度在最坏情况下是指数函数。现在遇到NP问题,通常用3种方法来解决:(1)设计一个算法和相应程序,只运行这个程序的一个小的实例。如背包问题算法;(2)设计一个算法和相应程序,只运行这个程序解决一个不太复杂的实例。如顶点覆盖问题算法;(3)设计一个近似算法。如:货郎担问题近似算法。本算法对于解决不