最短路径.ppt

《最短路径.ppt》由会员分享，可在线阅读，更多相关《最短路径.ppt（17页珍藏版）》请在三一办公上搜索。

1、,1,7.6 最短路径,应用背景：交通咨询、导航约定 有向图 设V0,1,n-1，边上的权值非负（长度）分类单源最短路径：1个源点到其余顶点的最短路径单目标最短路径：将各边反向，即为问题1单点对间最短路径：可用来解，但二者渐近时间相同所有点对间最短路径：亦可用来解，即每个顶点作为源点调用,2,7.6.1 单源最短路径问题,观察,上表是按路径长度递增序产生的从源点到其余顶点的最短路径0到4的路径：,长度：100，90，70，60规律：当按长度增序生成从源s到其它顶点的最短路径时，则当前正在生成的最短路径上除终点外，其余顶点的最短路径均已生成例子：当求0到2的最短路径时，则该路径上顶点0,3的最短

2、路径在此前已生成,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到某白点的路径不存在，可假设该白点的最短路径是一条长度为的虚拟

3、路径。,4,7.6.1 单源最短路径问题,如何扩充红点集？白点k的最短路径上除终点外，其余顶点的最短路径均已生成，故它们均为红点设置向量D0.n-1，对每一个白点vV-S，用Dv记录从源点s到达v，且除v外中间不经过任何白点的“最短”路径长度。初始时每个白点v的Dv值是边上的权。Note：从s到v的中间不经过其他白点的路径可能不止1条，但只需将其中最短的那条的长度记录在Dv中。Dv=SDv？即Dv是v最终的最短距离吗？不一定，因为s到v可能存在包含其它白点作为中间点的更短路径。Dv只是v当前估计的最短距离（简称估计距离），即：DvSDv如何在当前白点集中选一最短距离最小的白点k来扩充红点集？,

4、5,如何扩充红点集？(续）Th.7.6.1 若k是白点集中估计距离最小的顶点，则k的估计距离就是最短距离。即：若Dk=min Di：iV-S，则Dk=SDkPf（反证法）：设Dk不是k的最短距离，则必存在一条路径P：s k，其长度：length(p)length(P)Dx，这与k是当前白点集中估计距离最小的顶点矛盾！k是最短距离最小的白点吗？定理保证了k加入红点集的正确性 贪心策略：每次选离源点“最近”的白点来扩充红点集,6,7.6.1 单源最短路径问题,如何调整白点集中白点的估计距离？由于新红点k可能导致剩余白点的估计距离变小，使之离源点更近，故需调整。设jV-S，若Dj由于k加入红点集而变

5、小，则新路径P必是s k j，且P1中只有红点，P2必是边，即：Length(p)=Dk+w.证明：略调整方法 若length(P)Dj，则用length(P)来修正Dj。,7,7.6.1 单源最短路径问题,例子,最短距离：红色估计距离：白色依次求出的最短距离为：D0=0D1=10，调整顶点2D3=30，调整顶点2，4D2=50，调整顶点4D4=60,最短路径树：各顶点的最短路径（实线）总是一棵以源点为根的树，称之为。,8,7.6.1 单源最短路径问题,如何构造最优解 因为D向量只记录了最优解的值，但不能得到最优解。因此，要记录最优解则须引入附加信息。因为最优解是最短路径树，故只需增加一个向量

6、P0.n-1,用Pi记录顶点i的双亲，由双亲的唯一性知，顶点i的最短路径可从Pi反复上溯至根（源点）即可求得最优解。算法实现 if 不是边 Gij=w()otherwise,9,7.6.1 单源最短路径问题,typedef int Distancen;typedef int Pathnvoid Dijkstra(AdjMatrix G,Distance D,Path P,int s)/0s n-1,若不是边，则Gij=Infinity Boolean Sn；/S是红点集。Si为真表示i为红点，否则为白点 for(i=0;iE,s是i的前驱(双亲)else Pi=-1;/i无前驱，注意Ps亦无前

7、驱 Ss=TRUE;Ds=0；/红点集仅有源点s,10,for(i=0;iDk+Gk j)D j=Dk+Gk j;/修改白点j的估计距离，使之离s更近 P j=k;/k是j的前驱/endfor,11,算法执行过程 源点s3时间：时间O(n2)构造解,12,输出路径及其长度void PrintPath（Path P，Distance D）/路径是逆向的 int i，pre;for(i=0;in;i+)/依次打印点i的最短路径及长度 printf(“nD:%d,P:%d”,Di,i);/输出终点i pre=Pi;/找终点i的前驱 while(pre!=-1)printf(“,%d”,pre);pr

8、e=Ppre;/上溯找前驱,构造解,13,7.6.2 所有点对间的最短路径问题,解法一以每一顶点为源点，调用DIjkstra算法，时间O(n3)解法二Floyd（1978年图灵奖得主）算法更简洁，但是时间仍为O(n3)假设：加权邻接矩阵C（nn）0 if i=j Cij=if 不是边 w()otherwise思想：i,jV，若E，则从i到j有一条路径，长度为Ci j 但它不一定是最短路径，因为可能存在一条从i到j中间包含其他顶点的更短路径。因此，必须依次考虑能否在i和j之间加入顶点0,1,n-1,而得到更短的路径。,14,Floyd算法的基本步骤 定义nn的方阵序列D1,D0,Dn1,初始化：

9、D1C D1ij边的长度，表示初始的从i到j的最短路径长度，即它是从i到j的中间不经过其他中间点的最短路径。迭代：设Dk1已求出，如何得到Dk（0kn1）？Dk1ij表示从i到j的中间点不大于k1的最短路径p：ij，考虑将顶点k加入路径p得到顶点序列q：ikj，若q不是路径或q是长度大于p长度的路径，则当前的最短路径仍是上一步结果：Dkij=Dk1ij；否则用q取代p作为从i到j的最短路径。因为q的两条子路径ik和kj皆是中间点不大于k1的最短路径，所以从i到j中间点不大于k的最短路径长度为：Dkijmin Dk1ij,Dk1ik+Dk1kj 矩阵序列D1,D0,Dn1可在同1个矩阵上迭代求得

10、，为什么？,15,7.6.2 所有点对间的最短路径问题,Floyd算法的基本步骤(续)解矩阵：Pathnn：记录路径构造 在第k次跌代中，Pij记录从i到j的中间点序号不大于k的最短路径上顶点i的后继顶点。当算法结束时，可由Pathij得到从i到j的最短路径，其方法是从顶点i开始反复找其后继，直至找到顶点j或确认i到j没有路径为止。,16,Floyd算法实现 void Floyd(AdjMatrix D,AdjMatrix C,int Pathnn)for(i=0;in;i+)for(j=0;jn;j+)/初始化 D i j=C i j;if(C i j=Infinity)Pathij=-1;

11、else Path i j=j;/j是i的后继/endfor for(k=0;kn;k+)/将k扩充到从i到j的最短路径上 for(i=0;in;i+)for(j=0;jn;j+)if(D i k+D k jD i j)D i j=D i k+D k j;/修改路径长度 Path i j=Path i k;/修改路径,17,void PrintPath(AdjMatrix D,int Pathnn)/不妨设D是整型矩阵for(i=0;i%d”,next);/输出后继顶点 next=Pathnextj;/继续找后继顶点/endwhile printf(“%-%d”,j);/输出终点/endif/endfor EX.7.11,7.13,7.42,