最短路径学习.pptx

《最短路径学习.pptx》由会员分享，可在线阅读，更多相关《最短路径学习.pptx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、17.6.1 单源最短路径问题观察01324103010020501060源点源点中间顶点中间顶点 终点终点长度长度011003300325003,2460上表是按路径长度递增序产生的从源点到其余顶点的最短路径上表是按路径长度递增序产生的从源点到其余顶点的最短路径0到到4的路径：的路径：,长度：长度：100，90，70，60规律规律：当按长度增序生成从源：当按长度增序生成从源s到其它顶点的最短路径时，则当前正到其它顶点的最短路径时，则当前正在生成的最短路径上除终点外，其余顶点的最短路径均已生成在生成的最短路径上除终点外，其余顶点的最短路径均已生成例子例子：当求：当求0到到2的最短路径时，则该路

2、径的最短路径时，则该路径上顶点上顶点0,3的最短路的最短路径在此前已生成径在此前已生成第1页/共17页27.6.1 单源最短路径问题约定 从源s到终点v的最短路径简称为v的最短路径，SP(v)s到v的最短路径长度简称为v的最短距离，SD(v)红点集S：最短距离已确定的顶点集合 白点集V-S：最短距离尚未确定的顶点集合算法思想-Dijkstra（1972图灵奖得主）基于上述观察初始化：仅已知源s的最短距离SD(s)=0，故红点集S=s;扩充红点集：算法的每一步均是在当前白点集中选一最短距离最小的白点来扩充红点集，以保证算法是按长度增序来产生各顶点的最短路径;结束：当前白点集空或仅剩下最短距离为的

3、白点为止。注：若s到某白点的路径不存在，可假设该白点的最短路径是一条长度为的虚拟路径。第2页/共17页37.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当前估计的最短距离

4、（简称估计距离），即：DvSDv如何在当前白点集中选一最短距离最小的白点k来扩充红点集？第3页/共17页47.6.1 单源最短路径问题如何扩充红点集？若k是白点集中估计距离最小的顶点，则k的估计距离就是最短距离。即：若Dk=min Di：iV-S，则Dk=SDkPf（反证法）设Dk不是k的最短距离，则必存在一条路径P：s k，其长度 Length(p)length(P)Dx，这与k是当前白点集中估计距离最小的顶点矛盾！k是最短距离最小的白点吗？定理保证了k加入红点集的正确性pp1p2第4页/共17页57.6.1 单源最短路径问题如何调整白点集中白点的估计距离？由于新红点k可能导致剩余白点的估计

5、距离变小，使之离源点更近，故需调整。设jV-S，若Dj由于k加入红点集而变小，则新路径P必是s k j，且P1中只有红点，P2必是边，即：Length(p)=Dk+w.证明：略调整方法 若length(P)Dj，则用length(P)来修正Dj。p1p2第5页/共17页67.6.1 单源最短路径问题例子012430101001003030100124301010010060603050103001324103010020501060012430109060505030201030012430106010505030201030最短距离：红色最短距离：红色估计距离：白色估计距离：白色依次求出的最

6、短距离为：依次求出的最短距离为：1)D0=02)D1=10，调整顶点调整顶点2 23)D3=30，调整顶点，调整顶点2，44)D2=50，调整顶点，调整顶点45)D4=60最短路径树：最短路径树：各顶点的最短路径（实线）总是一棵以源点为根的树，称之各顶点的最短路径（实线）总是一棵以源点为根的树，称之为最短路径树。为最短路径树。第6页/共17页77.6.1 单源最短路径问题如何构造最优解 因为D向量只记录了最优解的值，但不能得到最优解。因此，要记录最优解则须引入附加信息。因为最优解是最短路径树，故只需增加一个向量P0.n-1,用Pi记录顶点的双亲，由双亲的唯一性知，顶点i的最短路径可从Pi反复上

7、溯至根（源点）即可求得最优解。算法实现 if 不是边 Gij=w()otherwise第7页/共17页87.6.1 单源最短路径问题void Dijkstra(AdjMatrix G,Distance D,Path P,int s)/0s n-1,若不是边，则Gij=Infinity Boolean Sn；/S是红点集。Si为真表示j为红点，否则为白点 for(i=0;in;i+)/初始化 Si=FALSE;Di=Gsi;/置初始的估计距离 if(DiInfinity)Pi=s;/s是i的前驱(双亲)else Pi=-1;/i无前驱，注意Ps亦无前驱 Ss=TRUE;Ds=0；/红点集仅有源点

8、s第8页/共17页9 for(i=0;in-1;i+)/向红点集S扩充n1个红点 min=Infinity;for(j=0;jn;j+)/选估计距离最小的白点k（离s最近）if(!S j&D j min)min=D j;k=j;if(min=Infinity)return;/白点集为空或只剩下无最短路径的点 Sk=TRUE;/k加入红点集 for(j=0;jDk+Gk j )D j =Dk+Gk j;/修改白点j的估计距离，使之离s更近 P j =k;/k是j的前驱 /endfor第9页/共17页10算法执行过程 源点s3时间：时间O(n2)构造解循环循环i红点集红点集SkD0 D1 D2 D

9、3 D4P0 P1 P2 P3 P4初始化初始化3 20 0 60-1 -1 3 -1 313,22 20 0 30-1 -1 3 -1 223,2,44 20 0 30-1 -1 3 -1 23同上同上 白白点点集集0,1中中所所有有点点的的估估计距离为计距离为，退出循环，退出循环01324103010020501060第10页/共17页11输出路径及其长度void PrintPath（Path P，Distance D）/路径是逆向的 int i，pre;for(i=0;in;i+)/依次打印点i的最短路径及长度 printf(“nD:%d,P:%d”,Di,i);/输出终点i pre=P

10、i;/找终点i的前驱 while(pre!=-1)printf(“,%d”,pre);pre=Ppre;/上溯找前驱 n构造解构造解第11页/共17页127.6.2 所有点对间的最短路径问题解法一以每一顶点为源点，调用DIjkstra算法，时间O(n3)解法二Floyd（1978年图灵奖得主）算法更简洁，但是时间仍为O(n3)假设：加权邻接矩阵C（nn）0 if i=j Cij=if 不是边 w()otherwise思想：i,jV，若E，则从i到j有一条路径，长度为Cij。但它不一定是最短路径，因为可能存在一条从i到j中间包含其他顶点的更短路径。因此，必须依次考虑能否在i和j之间加入顶点0,1

11、,n-1,而得到更短的路径。第12页/共17页137.6.2 所有点对间的最短路径问题Floyd算法的基本步骤 定义nn的方阵序列D1,D0,Dn1,初始化：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

12、的最短路径，所以从i到j中间点不大于k的最短路径长度为：Dkijmin Dk1ij,Dk1ik+Dk1kj 矩阵序列D1,D0,Dn1可在同1个矩阵上迭代求得，为什么？第13页/共17页147.6.2 所有点对间的最短路径问题Floyd算法的基本步骤解矩阵：Pathnn：记录路径构造 在第k次跌代中，Pij记录从i到j的中间点序号不大于k的最短路径上顶点i的后继顶点。当算法结束时，可由Pathij得到从i到j的最短路径，其方法是从顶点i开始反复找其后继，直至找到顶点j或确认i到j没有路径为止。第14页/共17页157.6.2 所有点对间的最短路径问题Floyd算法实现 void Floyd(A

13、djMatrix 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;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;/修改路径 第15页/共17页167.6.2 所有点对间的最短路径问题Floyd算法实现 void PrintPath(AdjMatrix D,int Pathnn)/不妨设D是整型矩阵 for(i=0;in;i+)for(j=0;j%d”,next);/输出后继顶点 next=Pathnext j;/继续找后继顶点 /endwhile printf(“%-%d”,j);/输出终点 /endif /endfor 第16页/共17页17感谢您的观看！第17页/共17页