《图的最短路径问题.ppt》由会员分享，可在线阅读，更多相关《图的最短路径问题.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图的最短路径图的最短路径数据结构与算法分析1最短路径问题输入输入:每条边上标记了每条边上标记了权权(weights)或或代价代价(costs)的图的图.输出输出:组成最短路径的边的序列组成最短路径的边的序列.例如例如:寻找两个指定顶点之间的最短路径寻找两个指定顶点之间的最短路径寻找从一个顶点寻找从一个顶点S到图中所有其他顶点的最短路径到图中所有其他顶点的最短路径寻找所有顶点对之间的最短路径寻找所有顶点对之间的最短路径我们介绍的算法将仅计算最短路径的长度我们介绍的算法将仅计算最短路径的长度,而而不记录实际路径不记录实际路径.2最短路径的定义用记号用记号d(A,B)表示从顶点表示从顶点 A 到到
2、B 的最的最短距离短距离.定义定义w(A,B)为边为边(A,B)的权的权.如果两点之间没有边如果两点之间没有边,那么那么w(A,B)=.3 求从某个源点到其余各点的最短路径 每一对顶点之间的最短路径 4单源最短路径在图在图 G 中给定一个顶点中给定一个顶点S,找出从找出从S到到G中所有其他中所有其他顶点的最短路径顶点的最短路径.Try 1:用某种顺序访问顶点用某种顺序访问顶点,计算了迄今为止所有计算了迄今为止所有顶点的最短路径顶点的最短路径,然后添加到下一个顶点然后添加到下一个顶点x的最短的最短路径路径.问题问题:已经处理了的顶点的最短路径中有可能经过已经处理了的顶点的最短路径中有可能经过x.
3、解决方案解决方案:如果以从如果以从 s 出发所到达的距离出发所到达的距离(递增递增)为为顺序，对各个顶点进行处理就能避免上述问题顺序，对各个顶点进行处理就能避免上述问题.5 求求从源点到其余各点的最短路径从源点到其余各点的最短路径的算法的基本思想的算法的基本思想:依依最短路径的长度最短路径的长度递增的次序求得递增的次序求得各条路径各条路径源点源点v1其中，从源点到从源点到顶点顶点v的最短路径的最短路径是所有最短路径中长度最短者。v26 在这条路径上，必定只含一条弧，并且这条弧的权值最小。下一条路径长度次短的最短路径最短路径的特点：路径长度最短的最短路径最短路径的特点：它只可能有两种情况：或者是
4、直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。7其余最短路径的特点：再下一条路径长度次短的最短路径最短路径的特点:它可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。8Dijkstras Algorithm ExampleEDCBA 0Initial 203100Process A1820350Process C1810350Process B1810350Pro
5、cess D1810350Process E9Dijkstras Implementation/Compute shortest path distances from s,/return them in Dvoid Dijkstra(Graph*G,int*D,int s)int i,v,w;for(i=0;iG.n();i+)Di=INFINITY;Ds=0;for(i=0;in();i+)/Do vertices v=minVertex(G,D);if(Dv=INFINITY)return;G-setMark(v,VISITED);for(w=G-first(v);wn();w=G-ne
6、xt(v,w)if(Dw (Dv+G-weight(v,w)Dw=Dv+G-weight(v,w);10Implementing minVertex问题问题:如何决定下一个最靠近的顶点如何决定下一个最靠近的顶点?(也就是也就是,寻找寻找未访问顶点最小未访问顶点最小D值值 minVertex)方法方法1:通过扫描整个包含通过扫描整个包含|V|个元素的表来搜索最小个元素的表来搜索最小值值.Cost:Q Q(|V|2+|E|)=Q Q(|V|2).方法方法 2:将未被处理的顶点以将未被处理的顶点以D值大小为顺序保存在一值大小为顺序保存在一个用最小堆实现的优先级队列中，可以使用个用最小堆实现的优先级队
7、列中，可以使用(log|V|)次搜索找出下一个最近顶点。每次改变次搜索找出下一个最近顶点。每次改变D(x)值时，都值时，都可以通过先删除再重新插入的方法改变顶点可以通过先删除再重新插入的方法改变顶点x在堆中在堆中的位置的位置.Cost:Q Q(|V|+|E|)log|V|)11Approach 1/Find min cost vertexint minVertex(Graph*G,int*D)int i,v;/Set v to an unvisited vertex for(i=0;in();i+)if(G-getMark(i)=UNVISITED)v=i;break;/Now find sm
8、allest D value for(i+;in();i+)if(G-getMark(i)=UNVISITED)&(Di e();/Heap array temp.distance=0;temp.vertex=s;E0=temp;/Initialize heap array minheap H(E,1,G-e();for(i=0;iG.n();i+)Di=INFINITY;Ds=0;for(i=0;in();i+)/Get distances do if(!H.removemin(temp)return;v=temp.vertex;while(G-getMark(v)=VISITED);G-s
9、etMark(v,VISITED);if(Dv=INFINITY)return;for(w=G-first(v);wn();w=G-next(v,w)if(Dw (Dv+G-weight(v,w)Dw=Dv+G-weight(v,w);temp.distance=Dw;temp.vertex=w;H.insert(temp);/Insert in heap 13每对顶点间的最短路径对任意顶点的对任意顶点的 u,v V,计算计算 d(u,v)的值的值.一种解决方法是使用一种解决方法是使用|V|次次 Dijkstras 算法算法,每次都从不同的顶点出发计算最短路径每次都从不同的顶点出发计算最短路径
10、.更好的方法是使用更好的方法是使用 Floyds 算法算法.定义定义k-path 为任意一条从顶点为任意一条从顶点v到到u的、中间顶点的、中间顶点序号小于序号小于k 的路径的路径.14求每一对顶点之间的最短路径弗洛伊德算法的基本思想是：从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径。15若存在，则存在路径vi,vj /路径中不含其它顶点若,存在，则存在路径vi,v1,vj /路径中所含顶点序号不大于1若vi,v2,v2,vj存在，则存在一条路径vi,v2,vj /路径中所含顶点序号不大于2 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。16Floyds Algorithm/Floyds all-pairs shortest paths algorithmvoid Floyd(Graph*G)int DG-n()G-n();/Store distances for(int i=0;in();i+)/Initialize for(int j=0;jn();j+)Dij=G-weight(i,j);/Compute all k paths for(int k=0;kn();k+)for(int i=0;in();i+)for(int j=0;jn();j+)if(Dij (Dik+Dkj)Dij=Dik+Dkj;17