资源描述
,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第,14,章 最短路径问题,单源最短路径,所有顶点对间的最短路径,1第14章 最短路径问题 单源最短路径,2,单源最短路径,非加权图的最短路径,加权图的最短路径,带有负权值的图,无环图,给出一个加权图和图上的一个节点,s,，找出,s,到图中每一节点的最短路径,2单源最短路径非加权图的最短路径 给出一个加权图和图上的一个,3,非加权的最短路径,采用广度优先搜索，它按层处理一层的所有结点：离起始结点最近的结点最先处理，距离最远的最晚处理。,具体过程：,从,s,到,s,的最短路径为,0,通过搜索,S,的所有邻接结点就能找到离,S,距离为,1,的所有结点,搜索离,S,距离为,1,的所有结点的邻接结点就能找到距离为,2,的节点,重复上述过程，直到所有节点都访问到为止,3非加权的最短路径采用广度优先搜索，它按层处理一层的所有结点,4,找,v,2,到其他节点的最短距离,V,2,V,0,V,5,V,1,V,3,V,4,V,6,0,V,2,V,0,V,5,V,1,V,3,V,4,V,6,0,1,1,V,2,V,0,V,5,V,1,V,3,V,4,V,6,0,1,1,2,2,V,2,V,0,V,5,V,1,V,3,V,4,V,6,0,1,1,2,2,3,3,4找v2到其他节点的最短距离V2V0V5V1V3V4V60V,5,存储设计,数组,distance,：记录从源点到达每个结点的最短距离。,数组,prev,：记录要到达此结点，必须到达的前一结点。,例如，对于上图中的结点,v4,，,prevv4,记录的是,v1,。也就是说，从源点到达,v4,必须先到,v1,。而,prevv1,记录的是,v0,，,prevv0,记录的是,v2,。从,prev,数组，我们可以追溯到这条路径。例如，对于,v4,，我们可以追溯到这条路径为,v2-v0-v1-v4,。,5存储设计数组distance：记录从源点到达每个结点的最短,6,过程抽象,unweightedShortDistance(start),for,（每个结点,v,）,distancev=,无穷大；,distancestart=0;,prevstart=0;,for(int curDistance=0;curDistance,结点数,;+curDistance)for(,每个结点,u),if(distanceu=curDistance),for(u,的每一个邻接点,v),if,（,distancev=,无穷大）,distancev=curDistanve+1,；,prevv=u,；,.,6过程抽象unweightedShortDistance(s,7,分析,算法的时间复杂度为,O,（,|V|E|,）。,算法效率之所以低的原因之一在于：为保证所有结点都找到了最短路径，算法假设最长的路径是经过所有的结点。,该算法效率之所以低的第二个原因在于：内层循环的设计。在处理距离为,d,的结点时，我们找到了所有距离为,d+1,的结点。但算法并没有利用这个成果，而在下一个循环周期中又用顺序查找的方法检查了所有结点，从中挑出距离为,d+1,的结点。这浪费了大量的时间。,7分析算法的时间复杂度为O（|V|E|）。,8,算法的改进,外层循环没必要执行,|V|,次，只要所有的结点都已找到了最短距离就可以了。,第二层循环也没必要执行,|V|,次，只要检查新找到最短路径的结点。用一个队列保存新找到路径的结点,8算法的改进外层循环没必要执行|V|次，只要所有的结点都已找,9,改进算法的伪代码,unweightedShortDistance(start),for,（每个结点,v,）,distance(v)=,无穷大；,distancestart=0;,start,入队,;,while,（队列非空）,取出队头元素存入,u,；,for(u,的每一个邻接点,v),if,（,distancev=,无穷大）,distancev=distanceu+1,；,prevv=u,；,v,入队；,.,9改进算法的伪代码unweightedShortDistan,10,邻接表中的实现,template,void adjListGraph,:unweightedShortDistance,(TypeOfVer start,TypeOfEdge noEdge)const,linkQueue q;,TypeOfEdge*distance=new TypeOfEdgeVers;,int*prev=new int Vers;,int u,sNo;,edgeNode*p;,for(int i=0;i Vers;+i)distancei=noEdge;,10邻接表中的实现template class TypeO,11,/,寻找起始结点的编号,for(sNo=0;sNo Vers;+sNo)if(verListsNo.ver=start)break;,if(sNo=Vers),cout ,起始结点不存在,next),if(distancep-end=noEdge),distancep-end=distanceu+1;,prevp-end=u;,q.enQueue(p-end);,/,输出最短路径,for(i=0;i Vers;+i),cout ,从,start ,到,verListi.ver ,的路径为,:endl;,printPath(sNo,i,prev);cout endl;,11/寻找起始结点的编号,12,队列的变化：,d2=0,0 5 d0=1,d5=1,1 3 d1=2,d3=2,3,4 d4=3,6 d6=3,6,空 算法结束,V,2,V,0,V,5,V,1,V,3,V,4,V,6,12队列的变化：V2V0V5V1V3V4V6,13,printPath,函数的实现,路径的存储不是正向的。即可以从第一个结点找到第二个结点，从第二个结点找到第三个结点，,。而是逆向存储的，即最后一个结点记住倒数第二个结点，倒数第二个结点记住倒数第三个结点，,。,适合用递归处理。于是我们定义了一个私有的递归成员函数,printPath,来输出这条路径。,13printPath函数的实现 路径的存储不是正向的。即可,14,template,void adjListGraph,:printPath(int start,int end,int prev)const,if(start=end),cout verListstart.ver;,return;,printPath(start,prevend,prev);,cout -verListend.ver;,14template class TypeOfVer,c,15,函数的输出,从,v2,到,v0,的路径为：,v2 v0,从,v2,到,v1,的路径为：,v2 v0-v1,从,v2,到,v2,的路径为：,v2,从,v2,到,v3,的路径为：,v2 v0 v3,从,v2,到,v4,的路径为：,v2 v0 v3 v4,从,v2,到,v5,的路径为：,v2 v5,从,v2,到,v6,的路径为：,v2 v0 v3 v6,V,2,V,0,V,5,V,1,V,3,V,4,V,6,15函数的输出从v2到v0的路径为：V2V0V5V1V3V4,16,时间复杂度,算法的主体是,while,循环，该循环一直执行到队列为空。而图中的每个结点都必须而且仅入队一次，因此该循环必须执行,|V|,个循环周期。,每个循环周期检查出队结点的所有边，整个,while,循环检查了图中所有的边。因此，,while,循环的运行时间为,O,（,|E|,）。前面的一些辅助工作，如初始化、寻找起始结点的编号等所需要的时间是,O,（,|V|,）。所以算法的总运行时间为,O,（,|V|+|E|,）。,16时间复杂度算法的主体是while循环，该循环一直执行到队,17,单源最短路径,非加权图的最短路径,加权图的最短路径,带有负权值的图,无环图,给出一个加权图和图上的一个节点,s,，找出,s,到图中每一节点的最短路径,17单源最短路径非加权图的最短路径 给出一个加权图和图上的一,18,Dijkstra,算法,保存了一个顶点集,S,。,S,中的顶点是已经找到了最短路径的顶点。,开始时，顶点集合,S,只包含源点一个顶点。,反复执行以下循环，直至顶点集,S,包含所有的顶点为止：对于在顶点集,V-S,中的每个顶点，考察新加入顶点集,S,中的结点是否有边到达自己。如果存在，则检查这条路径是否比原来已知的路径要短。如果是，则更新源点到此结点的距离和路径；然后，从,V,S,中寻找一个路径最短的结点，从源点到这个结点已经不可能有更好的路径了，把它加入顶点集,S,18Dijkstra算法保存了一个顶点集S。S中的顶点是已经,19,4,V,2,V,0,V,5,V,1,V,3,V,4,V,6,4,2,1,2,5,3,10,2,4,8,1,6,5,4,V,2,V,0,V,5,V,1,V,3,V,4,V,6,4,2,1,2,5,3,10,2,4,8,1,6,5,6,5,4,V,2,V,0,V,5,V,1,V,3,V,4,V,6,4,2,1,2,5,3,10,2,4,8,1,6,5,6,5,4,V,2,V,0,V,5,V,1,V,3,V,4,V,6,4,2,1,2,5,3,10,2,4,8,1,6,5,6,5,7,9,194V2V0V5V1V3V4V64212531024816,20,4,V,2,V,0,V,5,V,1,V,3,V,4,V,6,4,2,1,2,5,3,10,2,4,8,1,6,5,6,5,7,9,4,V,2,V,0,V,5,V,1,V,3,V,4,V,6,4,2,1,2,5,3,10,2,4,8,1,6,5,6,5,7,9,4,V,2,V,0,V,5,V,1,V,3,V,4,V,6,4,2,1,2,5,3,10,2,4,8,1,6,5,6,5,7,9,204V2V0V5V1V3V4V64212531024816,21,存储设计,和非加权图的实现中一样，需要保存的距离和路径信息,还需要保存哪些结点在,S,中，哪些结点不在,S,中的信息。,设计三个数组：,distance,、,prev,和,known,，,21存储设计和非加权图的实现中一样，需要保存的距离和路径信息,22,伪代码,void dijkstra(start),for,（图中的每个顶点,v,）,distancev=INFINITY;,knownv=false;,distancestart=0;,for(i=1;i Vers;+i),v=,所有,known,标记为,false,的结点中的路径最短者；,knownv=true;,for,（,v,的每一个邻接点,w,）,if(knownw,等于,false&,distancev+(v,w),的权值,distancew),distancew=distancev+(v,w),的权值,Prevw=v;,22伪代码void dijkstra(start),23,邻接表类中实现的,Dijkstra,算法,template,void adjListGraph,:dijkstra(TypeOfVer start,TypeOfEdge noEdge)const,TypeOfEdge*distance=new TypeOfEdgeVers;,int*prev=new int Vers;,bool*known=new boolVers;,int u,sNo,i,j;,edgeNode*p;,TypeOfEdge min;,for(i=0;i Vers;+i)/,初始化,knowni=false;,distancei=noEdge;,23邻接表类中实现的Dijkstra算法 template,24,for(sNo=0;sNo Vers;
展开阅读全文