87.6最短路径 87.6.1单源最短路径问题 ·应用背景：交通咨询、导航 观察 源点中间顶点终点长度 约定 10 有向图 3 30 设V={0,1,n-1,边上的权值非负（长度） 3 2 50 2 32 0■ 60 ■分类 ①单源最短路径：1个源点到其余顶点的最短路径 上囊是按路径长度递增序产生的从源点到其余顶点的最短路径 ②单目标量短路径：将各边反向，即为问题1 0到4的路径：<0,4，<0,3,4>，<0,1,2,4>，<0,3,2,4> 长度：100,90， 70, 60 ®单点对间量短路径：可用①来解，但二者渐近时间相同 规绵：当按长度增序生成从源s到其它顶点的量短路径时，则当前正 ④所有点对间量短路径：亦可用①来解，即每个顶点作为源点 在生成的量短路径上雕线点外，其余顶点的最短路径均已生成 调用① 例子：当求0到2的量短路径时，则该路径<0,3,22上项点0,3的量短路 径在此前已生成 S7.6.1单源最短路径问题 S7.6.1单源最短路径问题 。约定 ·如何扩充红点篇？ 从源s到货点V的最短路径筒称为V的最短路径，SPM :白点k的量短路径上除线点外，其余顶点的量短路径均已生成，故它们均 s到v的最短路径长度简称为v的量短距真，SD) 为红点 红点集S:最短距离已确定的顶点靠合 设量向量D[0.m1],对每一个白点v∈V-S,用D[】记录从漂点到达y, 且除外中间不经过任何白点的“量短”路径长度。初始时每个白点的 自点纂VS:景短距离尚未痛定的顶点桌合 D[门值是边<a,>上的权。 算法惠想-D可jkstra(1972图灵奖得主) 基于上述现察 ◆初化，仅已知源s的最短距离SDs片0，收红点编S-s D片SD?即D是v量线的量知距离吗？不一定，因为s到v可能存在 包含其它白点作为中间点的更短路径， 某梦叠麦凌整这餐接绵建器量锅农的白点 D只是v当前估计的最短距离（简称估计距离），即：D≥80[ 锅整等餐5揭的货进的喜智 ◆如何在当前白点集中选一康短距实量小的白点收来扩充红点第？ 3 S7.6.1单源最短路径问愿 §7.6.1单源最短路径问题 ■如何扩充红点集？ 需7著亮的的 ■如何调整白点集中白点的估计距离？ P叫（反证法） 由于新红点k可能导致剩余白点的估计距高变小，使之离源点更 近，故需调整， 设DJ不是k的最短距离，测必存在一条路径P:喜吧一k,其长度 Longth(p)④0]试) 设Hj∈V-S,若D门由于k加入红点集而变小，则新路径P必是 由D]定义知，P至少包含1个白点作为中间点，不坊设x是P上第1个白点，则P sLk2j,且P1中只有红点，P2必是边<kP,即： 可分解为：■一L一x,x卫2一k,其中叫中仅有x为白点，由D[x]定义知 Longth(p)=Dk]+w,j》.证明：略 1nehP1]D,又因权为非负，放1nthP2]≥0，所以 longth(P)=longth (P1)+length (P2≥D[x】(试2 ◆调整方法 费得.D山网≥p,这与k是省前白点集中估计E离最小的 若longth (F)D[j],则用length(P)来修正D[j] k是量短距真量小的白点吗？ 定理保证了k加入红点集的正确性 1
1 1 §7.6 最短路径 应用背景：交通咨询、导航 约定 有向图 设V＝{0,1,…,n-1}，边上的权值非负（长度） 分类 ①单源最短路径：1个源点到其余顶点的最短路径 ②单目标最短路径：将各边反向，即为问题1 ③单点对间最短路径：可用①来解，但二者渐近时间相同 ④所有点对间最短路径：亦可用①来解，即每个顶点作为源点 调用① 2 §7.6.1 单源最短路径问题 观察 0 1 2 3 4 10 30 100 20 50 10 60 0 3,2 4 60 0 3 2 50 0 3 30 0 1 10 源点 中间顶点 终点 长度 上表是按路径长度递增序产生的从源点到其余顶点的最短路径 0到4的路径：<0,4>, <0,3,4>, <0,1,2,4>, <0,3,2,4> 长度： 100， 90， 70， 60 ¾ 规律：当按长度增序生成从源s到其它顶点的最短路径时，则当前正 在生成的最短路径上除终点外，其余顶点的最短路径均已生成 ¾ 例子：当求0到2的最短路径时，则该路径<0,3,2>上顶点0,3的最短路 径在此前已生成 3 §7.6.1 单源最短路径问题 约定 从源s到终点v的最短路径简称为v的最短路径，SP(v) s到v的最短路径长度简称为v的最短距离，SD(v) 红点集S：最短距离已确定的顶点集合 白点集V-S：最短距离尚未确定的顶点集合 算法思想- Dijkstra（1972图灵奖得主） 基于上述观察 初始化：仅已知源s的最短距离SD(s)=0，故红点集S={s}; 扩充红点集：算法的每一步均是在当前白点集中选一最短距离最小的白点 来扩充红点集，以保证算法是按长度增序来产生各顶点的最短路径; 结束：当前白点集空或仅剩下最短距离为∞的白点为止。注：若s到某白 点的路径不存在，可假设该白点的最短路径是一条长度为∞的虚拟路径。 4 §7.6.1 单源最短路径问题 如何扩充红点集？ ∵白点k的最短路径上除终点外，其余顶点的最短路径均已生成，故它们均 为红点 ∴设置向量D[0..n-1]，对每一个白点v∈V-S，用D[v]记录从源点s到达v， 且除v外中间不经过任何白点的“最短”路径长度。初始时每个白点v的 D[v]值是边<s,v>上的权。 Note：从s到v的中间不经过其他白点的路径可能不止1条，但只需将其中最 短的那条的长度记录在D[v]中。 D[v]=SD[v]？即D[v]是v最终的最短距离吗？不一定，因为s到v可能存在 包含其它白点作为中间点的更短路径。 D[v]只是v当前估计的最短距离（简称估计距离），即：D[v]≥SD[v] 如何在当前白点集中选一最短距离最小的白点k来扩充红点集？ 5 §7.6.1 单源最短路径问题 如何扩充红点集？ Th.7.6.1 若k是白点集中估计距离最小的顶点，则k的估计距离就是最短距 离。即：若D[k]=min{ D[i]：∀i∈V-S }，则D[k]=SD[k] Pf（反证法） 设D[k]不是k的最短距离，则必存在一条路径P：s k，其长度 Length(p)<D[k] (式1) 由D[k]定义知，P至少包含1个白点作为中间点，不妨设x是P上第1个白点，则P 可分解为： s x， x k。其中P1中仅有x为白点，由D[x]定义知 length[P1]≥D[x]，又因权为非负，故length[P2]≥0，所以 length(P)=length(P1)+length(P2)≥ D[x] (式2) 由式1,2得：D[k]>length(P)≥D[x]，这与k是当前白点集中估计距离最小的顶 点矛盾！ k是最短距离最小的白点吗？ 定理保证了k加入红点集的正确性 p p1 p2 6 §7.6.1 单源最短路径问题 如何调整白点集中白点的估计距离？ 由于新红点k可能导致剩余白点的估计距离变小，使之离源点更 近，故需调整。 设∀j∈V-S，若D[j]由于k加入红点集而变小，则新路径P必是 s k j，且P1中只有红点，P2必是边<k,j>，即： Length(p)= D[k] + w<k,j>. 证明：略 调整方法 若length(P)<D[j]，则用length(P)来修正D[j]。 p1 p2
§7.6.1单源最短路径问题 10 §7.6.1单源最短路径问题 例子 ■如何构造最优解 100 100 因为D向量只记录了最优解的值，但不能得到量优解。因 100 301 ②20 此，要记录量优解则须引入附加信意。 因为最优解是最短路径树，故只需增加一个向量P0.-1]: ② ①30 ③0 量短距离：红色 用P可记录顶点的双亲，由双亲的唯一性知，顶点的康短路 估计距离：白色 径可从P可反复上期至根（源点）即可求得最优解。 依次求出的距离 ■算法实现 0(0 1)D[0- 90 60 2)D叫-10，题项点2 10 33-30,点2， 计<1j>不是边 5o② 203 )D叫2-50，调项点4 5)D4-60 G= w(<i,j>)otherwise 最短略径铜：各顶点的量短略径（实辣）总是一操以源点为极的树，称之 为最短径制 §7.6.1单源最短路径问题 for(i=0:iKn-1:t+)(向红点编s扩充n-1个红点 min=Infinity: void Dijkstra AdjMatrix G,Distance D,Path P,int s for(j户0；j水n:j计+)i选估计距离最小的白点k(离s绿近) 0≤s≤n-i,若iP不是边，测G可=Infinity if (IS[j]&&D[j]<min ) Boolean S[n:S是红点靠，S门为真囊示j为红点，香剩为白点 min=D[j];k=j for(i户0；iKn;it+)(谢化 if(min=Infinity)return;l自点集为空或只剩下无最知路径的点 S[=FALSE; S[k]=TRUE:∥k加入红点集 D叮=GS]门：量物输的估计距童 for(j户0：j长n:jt+)调雕测徐白点的估计距离 if (IS[j]&&D[j]>D[k]+G[k][j]){ f(D门<nfinity）P可=s;s是的前厦履亲) D[j门=DK+Gj小：修改白点的估计距离，使之离s更近 else P门=-1；∥无前图，注意Ps)亦无前驱 P[j】=k:∥k是的前星 Mlendfor Ss]=TRUE;D[S]=O:红点靠仅有源点s ■算法执行过理 ■构造解 原点s=3 精出路径及其长度 铺环 红点集S D[O]D[1]D[2]D[3]D[4] POPI1)P2P3)P间 void PrintPath(Path P,Distance D)(路径是逆向的 inti,pre; 初始化 3) °20060 11313 for(=0:iK;i计+)（依次打印点的量短路径及长度 43-12 printf(nD:%d,P:%d”,D0,:输出鳞点i 3,2 pre=P门：I/找绕点的前驱 3,24 4 1 2 while pre=-1){ printf(",%d”,preH 同上 白点靠0,1)中所有点的估 pre=Ppro:I上测找前驱 计距离为©，退出量环 时间：时间0（的 。构造解 2 2
2 7 §7.6.1 单源最短路径问题 例子 0 1 2 4 3 0 10 100 100 ∞ 30 30 10 0 1 2 4 3 0 10 100 100 60 30 50 10 30 0 1 2 3 4 10 30 100 20 50 10 60 0 1 2 4 3 0 10 90 60 50 30 20 10 30 0 1 2 4 3 0 10 60 10 50 30 20 10 30 最短距离：红色 估计距离：白色 依次求出的最短距离为： 1) D[0]=0 2) D[1]=10，调整顶点2 3) D[3]=30，调整顶点2，4 4) D[2]=50，调整顶点4 5) D[4]=60 ¾ 最短路径树：各顶点的最短路径（实线）总是一棵以源点为根的树，称之 为最短路径树。 8 §7.6.1 单源最短路径问题 如何构造最优解 因为D向量只记录了最优解的值，但不能得到最优解。因 此，要记录最优解则须引入附加信息。 因为最优解是最短路径树，故只需增加一个向量P[0..n-1], 用P[i]记录顶点的双亲，由双亲的唯一性知，顶点i的最短路 径可从P[i]反复上溯至根（源点）即可求得最优解。 算法实现 ∞ if <i,j>不是边 G[i][j]= w(<i,j>) otherwise 9 §7.6.1 单源最短路径问题 void Dijkstra ( AdjMatrix G, Distance D, Path P, int s ){ //0≤s ≤n-1,若<i,j>不是边，则G[i][j]=Infinity Boolean S[n]；//S是红点集。S[i]为真表示j为红点，否则为白点 for ( i=0; i<n; i++) { //初始化 S[i]=FALSE; D[i]=G[s][i]; //置初始的估计距离 if ( D[i]<Infinity ) P[i]=s; //s是i的前驱(双亲) else P[i]=-1; // i无前驱，注意P[s]亦无前驱 } S[s]=TRUE; D[s]=0；//红点集仅有源点s 10 for ( i=0; i<n-1; i++) { //向红点集S扩充n－1个红点 min=Infinity; for ( j=0; j<n; j++ ) //选估计距离最小的白点k（离s最近） if ( !S[ j ]&&D[ j ]<min ) { min=D[ j ]; k=j; } if (min==Infinity) return; // 白点集为空或只剩下无最短路径的点 S[k]=TRUE; // k加入红点集 for ( j=0; j<n; j++ ) //调整剩余白点的估计距离 if ( !S[ j ]&&D[ j ]>D[k]+G[k][ j ] ) { D[ j ] = D[k]+G[k][ j ]; //修改白点j的估计距离，使之离s更近 P[ j ] = k; // k是j的前驱 } }//endfor } 11 算法执行过程 源点s＝3 时间：时间O(n2) 构造解 白点集{0,1}中所有点的估 计距离为∞，退出循环 3 同上 － 2 {3,2,4} 4 ∞ ∞ 20 0 30 -1 -1 3 -1 2 1 {3,2} 2 ∞ ∞ 20 0 30 -1 -1 3 -1 2 初始化 {3} － ∞ ∞ 20 0 60 -1 -1 3 -1 3 循环i 红点集S k D[0] D[1] D[2] D[3] D[4] P[0] P[1] P[2] P[3] P[4] 0 1 2 3 4 10 30 100 20 50 10 60 12 输出路径及其长度 void PrintPath（Path P，Distance D）{ //路径是逆向的 int i，pre; for ( i=0; i<n; i++ ) { //依次打印点i的最短路径及长度 printf(“\nD:%d, P:%d”, D[i], i); //输出终点i pre=P[i]; //找终点i的前驱 while ( pre != -1 ) { printf( “, %d”, pre ); pre=P[pre]; //上溯找前驱 } } } 构造解
S7.6.2所有点对间的最短路径问题 §7.6.2所有点对间的最短路径问题 Floyd算法的基本步骤 ■解法一 定义nXn的方阵序列D_-,D。:.Da-中 以每一顶点为源点，调用Dljkstra]算法，时间o(n内 ◆韧抛化1D-,=C ·解法二 D-门叩=边<P的长度，表示初谢的从到的量短略径长虚，即它是从 F1oyd(1978年量现莫得主)算法更前清，但是时间仍为0(n习 到的中间不经过其他中间点的量短路径， 假设，加权邻被矩阵C(n×n) ◆选代：设Dk-,已求出，如何得到D,(0≤k≤n一1)？ o 谱问 Dk-门门表示从到的中间点不大于k一1的量细路径p:1.: c 计<P不是边 考律将项点k加入路径即得到顶点序列qi.k.可， w(<i,j)otherwise 费干六精为留上- ◆思想 IJ∈V,若<J>∈E,测从到南一条路径，长度为C间门。 乐绿舞经点不大于一尚准造显 景及鞋牌 D]=min{D.[D-m[k]+D-[k]0]) 到更短的路径。 矩阵序列D-D6,…D。-可在同1个矩阵上选代求得，为什么？ §7.6.2所有点对间的最短路径问题 S7.6.2所有点对间的最短路径问题 Floyd算法的基本步霖 Floyd算法实现 ◇解矩阵 void Floyd(AdjMatrix D,AdjMatrix C,int Path[n][n]) for (i=0;i<n;i++) Path[nJ[n]:记录路径构造 for(j户0：jKn;j计+)（初输化 在第k次跌代中，P门叮记录从到的中间点序号不大于k D[[=C[[: 的量短路径上顶点的后键顶点。 if C[]=Infinity Path[=-1; 当算法结束时，可由Path叮们得到从到的最短路径，其 else Path[时所是i的后健 方法是从顶点开始反复找其后罐，直至找到顶点或确认到 Mendfor for(k=0;k<n:k+)将k扩充到从到的量短路径上 没有路径为止。 for i=0;i<n;++) for (j=0:j<n;j++) f(D[Ik灯+D[k灯[<D[[)( D[(=D[灯+D[k[小：修效略径长度 Pat曲h[[=Path】Ik灯：修政廉径 S7.62所有点对间的最短路径问题 ■Floyd算法实现 void PrintPath(AdjMatrix D,int Path[n][)不妨设D是蓝矩时 for (E0;kn;+) for(J=0;n;++){ prn“%d,D】方到的绿烟哪径长底 next=Path[]Nn 为点的后 什(next=,1)n无后健爽示剩无略径 printf (%d to %d no path.In",I,)t else pin“%d",i)方输出起点 while next = print“->%d,next片输出后项点 next-Path[next刘0：银蝶线后鞭顶点 】fendwhile pin“%->%d",J:物出峰点 }lendif }endfor 3
3 13 §7.6.2 所有点对间的最短路径问题 解法一 以每一顶点为源点，调用DIjkstra算法，时间O(n3) 解法二 Floyd（1978年图灵奖得主）算法更简洁，但是时间仍为O(n3) 假设：加权邻接矩阵C（n×n） 0 if i=j C[i][j]= ∞ if <i,j>不是边 w(<i,j>) otherwise 思想： ∀i,j∈V，若<i,j>∈E，则从i到j有一条路径，长度为C[i][j]。 但它不一定是最短路径，因为可能存在一条从i到j中间包含其他顶点的 更短路径。因此，必须依次考虑能否在i和j之间加入顶点0,1…,n-1,而得 到更短的路径。 14 §7.6.2 所有点对间的最短路径问题 Floyd算法的基本步骤 定义n×n的方阵序列D－1, D0 , … Dn－1, 初始化： D－1＝C D－1[i][j]＝边<i,j>的长度，表示初始的从i到j的最短路径长度，即它是从i 到j的中间不经过其他中间点的最短路径。 迭代：设Dk－1已求出，如何得到Dk（0≤k≤n－1）？ Dk－1[i][j]表示从i到j的中间点不大于k－1的最短路径p：i…j， 考虑将顶点k加入路径p得到顶点序列q：i…k…j， 若q不是路径或q是长度大于p长度的路径，则当前的最短路径仍是上一步 结果：Dk[i][j]= Dk－1[i][j]；否则用q取代p作为从i到j的最短路径。 因为q的两条子路径i…k和k…j皆是中间点不大于k－1的最短路径， 所以从i到j中间点不大于k的最短路径长度为： Dk[i][j]＝min{ Dk－1[i][j], Dk－1[i][k] +Dk－1[k][j] } 矩阵序列D－1, D0 , … Dn－1可在同1个矩阵上迭代求得，为什么？ 15 §7.6.2 所有点对间的最短路径问题 Floyd算法的基本步骤 解矩阵： Path[n][n]：记录路径构造 在第k次跌代中，P[i][j]记录从i到j的中间点序号不大于k 的最短路径上顶点i的后继顶点。 当算法结束时，可由Path[i][j]得到从i到j的最短路径，其 方法是从顶点i开始反复找其后继，直至找到顶点j或确认i到j 没有路径为止。 16 §7.6.2 所有点对间的最短路径问题 Floyd算法实现 void Floyd( AdjMatrix D, AdjMatrix C, int Path[n][n] ) { for ( i=0; i<n; i++ ) for ( j=0; j<n; j++ ) { //初始化 D[ i][ j]=C[ i][ j]; if ( C[ i][ j]=Infinity ) Path[i][j]=-1; else Path[ i][ j]=j; //j是i的后继 }//endfor for ( k=0;k<n;k++ ) //将k扩充到从i到j的最短路径上 for ( i=0;i<n;i++ ) for ( j=0;j<n;j++ ) if ( D[ i][ k]+D[ k][ j]<D[ i][ j] ) { D[ i][ j]=D[ i][ k]+D[ k][ j]; //修改路径长度 Path[ i][ j]=Path[ i] [ k]; //修改路径 } } 17 §7.6.2 所有点对间的最短路径问题 Floyd算法实现 void PrintPath( AdjMatrix D, int Path[n][n] ) {//不妨设D是整型矩阵 for ( i=0; i<n; i++ ) for ( j=0; j<n; j++ ) { printf( “%d”, D[ i][ j] ); //i到j的最短路径长度 next=Path[i][j]；//next为起点i的后继 if （ next == -1 ）//i无后继表示i到j无路径 printf（“%d to %d no path.\n”, i, j ）； else { printf( “%d”, i ); //输出起点 while ( next != j ){ printf( “->%d”, next ); //输出后继顶点 next=Path[next][j]; //继续找后继顶点 } //endwhile printf( “%->%d”, j ); //输出终点 } //endif } //endfor }