87.6最短路径 87.6.1单源最短路径问题 ·应用背景:交通咨询、导航 观察 源点中间顶点终点长度 约定 10 有向图 3 30 设V={0,1,n-1,边上的权值非负(长度) 3 2 50 2 32 0■ 60 ■分类 ①单源最短路径:1个源点到其余顶点的最短路径 上囊是按路径长度递增序产生的从源点到其余顶点的最短路径 ②单目标量短路径:将各边反向,即为问题1 0到4的路径:,, 长度:100,90, 70, 60 ®单点对间量短路径:可用①来解,但二者渐近时间相同 规绵:当按长度增序生成从源s到其它顶点的量短路径时,则当前正 ④所有点对间量短路径:亦可用①来解,即每个顶点作为源点 在生成的量短路径上雕线点外,其余顶点的最短路径均已生成 调用① 例子:当求0到2的量短路径时,则该路径上的权。 算法惠想-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的路径:, , , 长度: 100, 90, 70, 60 ¾ 规律:当按长度增序生成从源s到其它顶点的最短路径时,则当前正 在生成的最短路径上除终点外,其余顶点的最短路径均已生成 ¾ 例子:当求0到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]值是边上的权。 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)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必是边,即: Length(p)= D[k] + w. 证明:略 调整方法 若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, 计不是边 5o② 203 )D叫2-50,调项点4 5)D4-60 G= w()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]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 不是边 G[i][j]= w() otherwise 9 §7.6.1 单源最短路径问题 void Dijkstra ( AdjMatrix G, Distance D, Path P, int s ){ //0≤s ≤n-1,若不是边,则G[i][j]=Infinity Boolean S[n];//S是红点集。S[i]为真表示j为红点,否则为白点 for ( i=0; iD[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-门叩=边∈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%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 不是边 w() otherwise 思想: ∀i,j∈V,若∈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的中间不经过其他中间点的最短路径。 迭代:设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%d”, next ); //输出后继顶点 next=Path[next][j]; //继续找后继顶点 } //endwhile printf( “%->%d”, j ); //输出终点 } //endif } //endfor }