图论与网络优化.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第五章 图论与网络优化,2,5-1,引论,5-2,图论基本概念,5-3,树及其优化问题,5-,4,最短路问题,5-,5,最大流问题,5-6,中国邮递员问题,3,5-3,树及其优化问题,一、树及其性质,在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是,树。,例,5.3,已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,4,如果用六个点,v,1,v,6,代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。,v,6,v,3,v,4,v,2,v,5,v,1,5,v,6,v,3,v,4,v,2,v,5,v,1,表示任意两个城市之间均可以通话，这个图必须,是,连通图,。并且，这个图必须是,无圈,的。否则，从,圈上任意去掉一条边，剩下的图仍然是六个城市的,一个电话网。下图是一个不含圈的连通图，代表了,一个电话线网。,6,定义,6,：,一个无圈的连通图叫做,树,。,树一般记为,T,作为树定义还可以有以下几种表述：,(1),T,连通且无圈或回路,；,(2),T,无圈且有,n,1,条边（如果有,n,个结点）；,(3),T,连通有,n,1,条边；,(4),T,无回路，但不相邻的两个结点之间联以一边，恰得一个圈；,(5),T,连通，但去掉,T,的任意一条边，,T,就不连通了；（,亦即，在点集合相同的图中，树是含边数最少的连通图。）,(6),T,的任意两个结点之间恰有一条初等链,7,下面介绍树的一些重要性质：,【,定理,5】,p,个顶点的树含,p,1,条边。,定理,5-1,设图,G,=,（,V,，,E,）是一个树,p(G),2,，那么图,G,中至少有两个悬挂点。,定理,5-2,图,G,=,（,V,，,E,）是一个树的充要条件是,G,不含圈，并且有且仅有,p,1,条边。,定理,5-3,图,G,=,（,V,，,E,）是一个树的充要条件是,G,是连通图，并且有且仅有,p,1,条边。,定理,5-4,图,G,是一个树的充分必要条件是任意两个顶点之间,有且仅有一条链,。,8,从以上定理，不难得出以下,结论,：,（,1,）从一个树中任意去掉一条边，那么剩下的图,不是连通图,，亦即，在点集合相同的图中，树是含边数最少的连通图,。,（,2,）在树中不相邻的两个点之间加上一条边，那么恰好得到一个,圈,。,9,定义,7,设图,K,=(,V,E,1,),是图,G,=(,V,E,),的,一个支撑子图,(,点相同并保持图的连通性,),，,如果图,K,=(,V,E,1,),是一个树,那么称,K,是,G,的一个支撑树,。,v,6,v,5,v,2,v,3,v,4,v,1,a,v,6,v,5,v,2,v,3,v,4,v,1,b,例如,图,5.10,b,是图,5.10,a,的一个支撑树,二、支撑树,显然,如果图,K,=(,V,E,1,),是图,G,=(,V,E,),的一个,支撑树,那么,K,的边数是,p(G,),1,，,G,中不属于支撑树,K,的边数是,q(G),p(G),+1,。,10,【,定理,6】,一个图,G,有支撑树的充要条件是,G,是,连通图,。,证明：,充分性,:,设图,G,是连通的，若,G,不含圈，则按照定义，,G,是一个树，从而,G,是自身的一个支撑树。若,G,含圈，则任取,G,的,一个圈，从该圈中任意去掉一条边，得到图,G,的一支撑子图,G,1,。若,G,1,不含圈，则,G,1,是,G,的一个,支撑树,。,若,G,1,仍然含圈，则任取,G,1,的一个圈，再从圈中任意去掉一条边，得到图,G,的一支撑子图,G,2,。依此类推，可以得到图,G,的一个支撑子图,G,K,，且不含圈，从而,G,K,是一个支撑树。,11,定理,6,充分性的证明，提供了一个寻找连通图支撑树的方法叫做“破圈法”,。,即：,就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。,例,4,用破圈法求出下图的一个支撑树。,v,5,v,4,v,2,v,3,v,1,e,6,e,5,e,4,e,3,e,2,e,1,e,7,e,8,12,取一个圈,(,v,1,v,2,v,3,v,1,),，在一个圈中去掉边,e,3,。,v,5,v,4,v,2,v,3,v,1,e,6,e,5,e,4,e,3,e,2,e,1,e,7,e,8,v,2,e,1,e,2,e,5,e,8,v,1,v,3,v,4,v,5,在剩下的图中，再取一个圈（,v,1,v,2,v,4,v,3,v,1,），去掉边,e,4,。,再从圈（,v,3,v,4,v,5,v,3,）中去掉边,e,6,。,再从圈,(,v,1,v,2,v,5,v,4,v,3,v,1,）中去掉边,e,7,。,这样，剩下的图不含圈，于是得到一个支撑树，如图所示。,13,1,最小支撑树,定义,8,：设图,G=,（,V,，,E,），,E,中任意一条边,e,ij,上都对应有一个数,w,ij,，称,w,ij,为,e,ij,的权重，权重的全体记作,W,，称为,G,上的权重集，简称权。图,G,称为赋权图。记作,G=,（,V,，,E,，,W,），,G,的总权重记作,w,（,G,），或者,w,（,E,）。,今后，我们讨论的都是连通的赋权图。,一个网络图可以有多个支撑树记,G,的所有支撑树的集合为：,T,T,k,|,k,1,，,2,，,，,L,三、最小支撑树及其算法,14,设,T,k,（,V,，,E,k,，,W,k,）是图,G,（,V,，,E,，,W,）的一棵支撑树，则边集,E,k,中所有边的权数之和称为树,T,k,的权数，记为：,则称,T,*,为图,G,的一棵最小支撑树。,定义,9,：图,G,的支撑树,T,中，总权最小的树称为最小支撑树，简称最小树，记作,T*,15,a,b,f,d,e,c,2,2,4,2,5,6,3,4,5,最小树,比如，城市间交通线的建造等，可以归结为这一类问题。,再如前面例,3,，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，这类问题的解决都可以归结为最小树问题。,16,【,定理,7】,树,T,*,是图,G,中最小树的充分必要条件是：,对,T*,外的每一条边,e,ij,，有下列不等式成立：,2,最小树的求法,根据定理,7,，可以得出求,T*,的两种算法：,（,1,）,Kruskal,算法（,1956,年，也称避圈法）：,每步取未选边中权最小的边且不构成圈，即：避圈留最小。,（,2,）,Rosenstiehl,算法（,1967,年，也称破圈法）：,每步弃所取圈中权重最大的边，即：破圈弃最大。,其中：,e,hk,是,T,*,中联通,v,i,与,v,j,的唯一链,C,ij,上的任意一条边。,17,(1),避圈法：,从图中任意节点开始寻找与该节点关联的权数,最小的边，,使之与以选边不构成为圈，直到选够,n,-1,条边为止。,例,最小树，权为,13,v,1,4,v,2,1,v,3,1,2,3,1,v,8,4,v,0,4,v,4,5,2,4,5,v,7,3,v,6,2,v,5,1,5,从网络中任选一点,v,1,v,2,v,3,v,4,v,5,v,6,v,1,v,3,v,1,v,3,v,2,v,1,v,3,v,2,v,5,v,6,v,1,v,3,v,2,v,5,v,6,v,4,v,1,v,3,v,2,v,5,19,(2),破圈法：,在图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；,去掉该圈中权数最大的边；,反复重复 两步，直到最小树。,v,1,4,v,2,1,v,3,1,2,3,1,v,8,4,v,0,4,v,4,5,2,4,5,v,7,3,v,6,2,v,5,1,5,最小树，权为,13,22,v,1,v,2,v,3,v,4,v,5,1,4,2,3,1,3,5,2,分别用两种方法求最小树,24,5-4,最短路问题,最短路问题是最重要的网络优化问题之一，它不仅可以直接应用于解决生产实际中的许多问题，如管道铺设、线路安排、厂区布局、设备更新等等，而且经常被作为一个基本工具，用于解决其它优化问题。许多优化问题往往可转化为求图上的最短路，这方面的研究工作已取得了十分丰富的成果，迄今为止，求解的算法已不下数十种。,25,如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从,v,1,出发，经过这个交通网到达,v,6,，要寻求总路程最短的线路。,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,26,从,v,1,到,v,6,的路线是很多的。比如,:,从,v,1,v,2,v,4,v,6,;,或者从,v,1,v,2,v,3,v,5,v,6,等等。,不同的路线，经过的总长度是不同的。,例如，按照第一个线路，总长度是,3+6+3=12,单位，,按照第二个路线，总长度是,3+1+1+6=11,单位。,因此，如何选择路线，使得总长度最短，便是本部分要讨论的问题。,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,27,一、有向图,【定义,10】,从点,u,到,v,的,有向线段,称为,弧,，记作：,a=(u,v),，其中，,u,与,v,分别称为弧,a,的始点与终点，图中所有弧的集合则记作,A,。弧,(v,i,v,j,),也常记作,a,ij,。,【定义,11】,非空点集,V,及其相应的,非空弧集,A,之二元组称为,有向图,，记作,D=(V,A),。,28,显然，给定一个有向图,D,，若去除弧上的方向，则对应得到唯一的无向图,G,。此时的,G,称为,D,的,基础图,；,反之，一个无向图,G,，由于可用不同的方式来标上方向，故可伴生多个有向图。无向图中的许多概念与术语（如链与圈等）可沿用于有向图中，但仍有一些不同之处。将有向图与其基础图相对照，有下列对应关系：,D,弧,路,回路,G,边,链,圈,29,在,D=(V,A),中，点,v,i,的,邻点集,N(v,i,),可分解为两部分，即：,当,D,为,简单图,时，,N(v,i,),、,N,+,(v,i,),、,N,-,(v,i,),常简记为,N,i,、,N,i,+,、,N,i,-,。,30,给定一个赋权有向图,D,(,V,，,A,),对每一条弧,a,ij,w,(,v,i,，,v,j,),，相应地有权,w,(,a,ij,)=,w,ij,，又有两点,v,s,、,v,t,V,设,r,是,D,中从,v,s,到,v,t,的一条路，路,r,的权是,r,中所有弧的权之和,记为,w,(r),最短路问题就是求从,v,s,到,v,t,的路中一条权最小的路,r,*,:,二、最短路问题,31,最短路问题按其不同的要求，可分成下列,三种类型,：,1,、求两个定点之间的最短路；,2,、求一个定点到其他各点的最短路；,3,、求各点对之间的最短路。,不失一般性，总假定图中无环，以及多重弧只是由两条互为反向的弧组成的二重弧。,32,【,例,4】,（渡河问题）,一人携带狼、羊、菜，须从一条小河的此岸渡往对岸。河边仅有一条小船，容量为,2,。当人不在场时，狼要吃羊、羊要吃菜。问：应怎样渡河，才能使大家安全到达对岸，且小船在河上的来回次数最少。,(,船上必须要有人,),33,【,解,】,记,M,代表人、,W,代表狼、,S,代表羊、,V,代表菜。,以河的此岸为考察基点，则开始状态为,MWSV,，结束状态为,。,共有,16,种状态：,MWSV,、,MWS,、,MWV,、,MSV,、,WSV,、,MW,、,MS,、,MV,、,WS,、,WV,、,SV,、,M,、,W,、,S,、,V,、,。,其中，有,6,种不允许出现，即：,WSV,、,MW,、,MV,、,WS,、,SV,、,M,。,于是，可能的状态仅有,10,种。,34,以每个状态作为顶点，构造相应的图（如图,5-8,所示），其中，边的连接原则为：,若状态甲经一次渡河可变为乙，则连一条边。,从而，渡河问题就归结为求,MWSV,的最短路。,(,船上必须要有人,),（算法形式化方面的内容）,图,5-8,MWSV,MWS,MWV,MSV,MS,WV,W,S,V,35,三、有向图最短路算法,1964,年，,Ford,提出了可求解含负权的最短路问题的递推标号法。,设赋权有向图,D=(V,A,W),，,V,中含,p,个点，现要求始点,v,1,至终点,v,p,的最短路,R,p,*,及其路长,r,p,*,。假定,D,中,无负回路,（其上总权为负数的回路），将原弧集,A,增广为新弧集，以使,V,中任意两点间均有互为反向的两条弧，同时权集,W,增广为新权集。于是，原图,D,增广为新图 。,36,其中，当,i=j,时，若设 ，则与实际背景不符，若,0,，则出现负回路，故须定义为,0,。由,Bellman,最优化原理易知：,从,v,1,到,v,j,的最短路长,r,j,*,必满足,反之亦然。,显见，若某两相邻点之间有多于一条的同向弧，则可弃大留小，简化为一条弧，从而是一个完全的二重赋权有向图，其中，增广的权集，定义为：,例：最短路径引例,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从1到8的最短路径,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,w,1,=0,min c,12,c,14,c,16,=min0+2,0+1,0+3=min2,1,3=1,其他为,X=1,4,w,4,=1,w,1,=0,w,1,=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,4,min c,12,c,16,c,42,c,47,=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2,X=1,2,4,w,2,=2,w,1,=0,w,4,=1,w,2,=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,min c,16,c,23,c,25,c,47,=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3,X=1,2,4,6,w,6,=3,w,2,=2,w,4,=1,w,1,=0,w,6,=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,min c,23,c,25,c,47,c,67,=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3,X=1,2,4,6,7,w,7,=3,w,2,=2,w,4,=1,w,1,=0,w,6,=3,w,7,=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,7,min c,23,c,25,c,75,c,78,=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6,X=1,2,4,5,6,7,w,5,=6,w,2,=2,w,4,=1,w,1,=0,w,6,=3,w,7,=3,w,5,=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,7,min c,23,c,53,c,58,c,78,=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8,X=1,2,3,4,5,6,7,w,3,=8,w,2,=2,w,4,=1,w,1,=0,w,6,=3,w,7,=3,w,5,=6,w,3,=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,3,4,6,7,min c,38,c,58,c,78,=min 8+6,6+4,3+7=min 14,10,11=10,X=1,2,3,4,5,6,7,8,w,8,=10,w,2,=2,w,4,=1,w,1,=0,w,6,=3,w,7,=3,w,5,=6,w,3,=8,w,8,=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,3,4,6,7,8,1,到10的最短路径为1，4，7，5，8，长度为10。,w,2,=2,w,4,=1,w,1,=0,w,6,=3,w,7,=3,w,5,=6,w,3,=8,w,8,=10,46,基本思路 ：,首先设任一点,v,i,到任一点,v,j,都有一条弧，如果在图,G,中，,(,v,i,v,j,),A,，则添加弧,(,v,i,v,j,),，并令,w,ij,=+,。,显然，从,v,1,到,v,j,的最短路是从,v,1,出发，沿着这条路到某个点,v,i,，再沿弧,(,v,i,v,j,),到,v,j,。则,v,1,到,v,i,的这条路必然也是,v,1,到,v,i,的最短路。否则，从,v,1,到,v,j,的这条路将,不是最短的。于是，设,r,j,表示从,v,1,到,v,j,的最短路长，,r,i,表示从,v,1,到,v,i,的最短路长，则有下列方程：,47,利用如下的递推公式：,开始时，令,即用,v,1,到,v,j,的直接距离做初始解。,从第二步起，使用递推公式：,求,当进行到第,t,步，若出现,：,则停止计算。,即为,v,1,到各点的最短路长。,48,计算步骤,：,Step 1.,初始标号,Step 2.,第,k+1,次标号,Step 3.,当成立,时，即得,从,v,p,出发，反向追踪，确定最短路,R,p,*,。,若,R,p,*,中,v,j,已确定，按式,确定前一点,v,i,；,否则，,k:=k+1,，转,Step 2,。,最后得到的标号就是,v1,到各点,vi,（,i=1,2,p,）的最短路长。,49,因已知图中顶点为,p,个，故算法至多经,(p 2)+1=p 1,次迭代必收敛。若一旦出现：,则说明,D,中必含负回路。在负回路上每循环一次，路长减少一个定值，永无休止，最终导致：,【,例,5】,求图,5-9,中从,v,1,到,v,8,的最短路。,图,5-9,v,1,v,2,v,6,v,3,v,4,v,5,1,-2,v,7,v,8,7,-3,-1,6,8,3,-3,-5,-1,-1,2,1,1,-5,2,50,解：,利用上面的递推公式，,将计算结果列出，如下表所示,(,空格为,+,),：,终点,始点,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,1,0,-1,-2,3,v,2,6,0,2,v,3,-3,0,-5,1,v,4,8,0,2,v,5,-1,0,-3,v,6,1,0,1,7,v,7,-1,0,-5,v,8,0,0,-1,-2,3,0,-5,-2,-7,1,-1,5,0,-5,-2,-7,-3,-1,-5,-2,0,-5,-2,-7,-3,-1,-5,-10,0,-5,-2,-7,-3,-1,-5,-10,v,1,v,2,v,6,v,3,v,4,v,5,1,-2,v,7,v,8,7,-3,-1,6,8,3,-3,-5,-1,-1,2,1,1,-5,2,51,可以看出，当,t,=,4,时，有：,因此，表中的最后一列，就是从,v,1,到,v,2,，,.,，,v,8,的最短路权。,从,v,8,出发，反向追踪，确定最短路,R,8,*,。,上述计算过程，不仅求得了两个定点之间的最短路，而且,同时得到一个定点至其他各点的最短路,。至于求各点对之间的最短路，则可重复应用上述计算法来解决。,v1,v2,v3,v4,v5,v6,v7,v8,0,1,2,3,4,R8*,v1,0,-1,-2,3,1,0,0,0,0,0,*,v2,6,0,2,2,-1,-5,-5,-5,-5,v3,-3,0,-5,1,3,-2,-2,-2,-2,-2,*,v4,8,0,2,4,3,-7,-7,-7,-7,*,v5,-1,0,-3,5,1,-3,-3,-3,v6,1,0,1,7,6,-1,-1,-1,-1,v7,-1,0,7,5,-5,-5,-5,*,v8,-5,0,8,-2,-10,-10,*,完整的计算表如下所示,(,表中没有数字的空格表示,+),。,于是得一条最短路,R8*=v1,v3,v4,v7,v8,，路长为,r8*=-10,。,52,四、无向图最短路算法,设,非负赋权简单图,G=(V,E,W),，,V,中含,p,个点，求始点,v,1,至终点,v,p,的最短路及其路长。,这里，介绍一种,固定标号法,（,Dijkstra,法）。,其要点是对点,v,i,(i1),用,两种标号,：,先用临时标号,t,i,(,是,v,1,到,v,i,最短路长的某个上界,),，,再用固定标号,r,i,(,是,v,1,到,v,i,的最短路长,),。,作一次迭代，就将至少一个,t,i,点变为,r,i,点（又称“将未着色点着色”）。,至多经,p 1,次迭代，,v,p,变为,r,p,*,点，于是得到,v,1,至,v,p,的最短路长，再反向追踪，定出最短路。,计算过程中，以,V,t,表示,t,i,点集，,V,t,中元素将由多变少，直至成为空集。,53,Dijkstra,算法的计算步骤如下：,Step 1.,始点,v,1,作固定标号,r,1,*=0,，其余点,v,j,作临时标号,t,j,=,，,V,t,=v,2,v,3,v,p,。,Step 2.,设当前已得到一个或多个,v,i,的固定标号,r,i,*,，对,v,j,N(v,i,)V,t,，修改,v,j,的临时标号为：,其中，右端的,t,j,是原值，左端的,t,j,是修改值。,Step 3.,对,v,j,V,t,，取：,为对应点,v,j,*,的固定标号，,V,t,:=V,t,-,v,j,*,。,Step 4.,当,V,t,=,时，得,r,p,*,，再从,v,p,出发，反向追踪，确定最短路,R,p,*,。若,R,p,*,中,v,j,已确定，按 式，确定前一点,v,i,；否则，转,Step 2,。,54,Dijkstra,算法示例：,求,v,1,到,v,6,的最短路,+,+,+,+,+,（,1,）首先给,v,1,以,r,标号,，,r(,v,1,),0,，给其余所有点,T,标号，,T,(,v,j,),（,j,=2,，,3,，,6),(0),r,标号以（）形式标在结点旁边，,T,标号以不带（）的数字标在结点旁边,.,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,实际上，所有点最后得到的固定标号正是,v,1,到各点的最短路路长。,用于有向图时，只要取,v,j,N,+,(v,i,)V,t,即可。,55,r(,v,2,)=,3,（,3,）,5,r(,v,3,)=,4,（,4,）,+,+,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,+,+,+,(0),9,（,2,）考察,v,1,:,T,(,v,2,)=,min,T,(,v,2,),，,r(,v,1,),+,a,12,min,，,0,3=3,T,(,v,3,)=,min,T,(,v,3,),，,r,(,v,1,),+,a,13,min,，,0,5=5,所以，,r,(,v,2,)=,3,（,3,）考察,v,2,:,T,(,v,3,)=,min,T,(,v,3,),，,r(,v,2,),+,a,23,min 5,，,3,1=4,T,(,v,4,)=,min,T,(,v,4,),，,r(,v,2,),+,a,24,min,，,3,6=9,所以，,r(,v,3,)=,4,T(,v,3,)=,5,T(,v,4,)=,9,56,r(,v,5,)=,5,（,3,）,（,4,）,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,+,+,(0),9,（,5,）,T(,v,4,)=,8,（,4,）考察,v,3,:,T,(,v,5,)=,min,T,(,v,5,),，,r(,v,3,),+,a,35,min,，,4,1=5,T,(,v,4,)=,min,T,(,v,4,),，,r(,v,3,),+,a,34,min 9,，,4,4=8,所以，,r(,v,5,)=,5,（,5,）考察,v,5,:,T,(,v,6,)=,min,T,(,v,6,),，,r(,v,5,),+,a,56,min,，,5,6=11,T,(,v,4,)=,min,T,(,v,4,),，,r(,v,5,),+,a,54,min 8,，,5,2=7,所以，,r(,v,4,)=,7,8,T(,v,6,)=,11,11,（,7,）,r(,v,4,)=,7,57,（,3,）,（,4,）,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,11,(0),（,5,）,（,7,）,（,6,）考察,v,4,:,T,(,v,6,)=,min,T,(,v,6,),，,r(,v,4,),+,a,46,min 11,，,7,3=10,所以，,r(,v,6,)=,10,所有点都标上,r,标号,r(,v,6,)=,10,(10),58,(7),标出最短路,v1,到,v6,的最短路可从,v1,开始，根据永久性标号数值回溯得到,最短路径是：,v,1,v,2,v,3,v,5,v,4,v,6,，路长,10,同时得到至其余各点的最短路，即各点的永久性标号,r,（,v,i,）,注意：,双标号法只适用于,所有,w,ij,0,的情形，当赋权有向图中存在负权时，则算法失效,（,3,）,（,4,）,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,(0),（,5,）,（,7,）,(10),59,由以上计算过程可知，每迭代一次，固定标号个数就会增加。作第,k+1,次迭代时，,在第,k,次迭代时才取得固定标号的点之各邻点的临时标号重又查视一遍，有的得以保留，而有的可能改进,。,最后，在当前所有临时标号中取出最小值，其对应的点就作为新增加的固定标号点。当然，一个最小值可对应多个点，从而，一次迭代有可能同时得到多个固定标号点，总迭代次数不超过,p,-1,。,60,【,例,7】,求图,5-11,所示图中从,v,1,至,v,8,的最短路及路长。,V,1,V,2,V,3,V,4,V,5,V,6,V,7,V,8,2,8,1,6,7,1,4,2,2,9,3,4,9,6,2,图,5-11,61,【,解,】,计算表如下：,0,1,2,3,4,5,6,7,R,8,*,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,V,1,V,2,V,3,V,4,V,5,V,6,V,7,V,8,2,8,1,6,7,1,4,2,2,9,3,4,9,6,2,图,5-11,表中空格对应的值为,+,，固定标号加方括弧，短横线格是同一行固定标号重复书写的简化，于是，得一条最短路,R,8,*,：,v,1,v,3,v,5,v,2,v,6,v,8,，,路长为,r,8,*=11,。,0,-,8,2,1,-,8,-,10,2,-,-,-,8,3,10,-,-,-,-,7,6,12,10,7,-,-,-,-,-,10,12,-,-,-,-,-,-,9,12,-,-,-,-,-,-,-,11,*,*,*,*,*,*,