数据结构42-最短路径.ppt

数 据 结 构第四十二课 最短路径 第三十四课 最短路径 本课主题：顶点之间的最短路径 教学目的：顶点之间的最短路径 教学重点：一个顶点到其它顶点间的最短路径及任意两 顶点间的最短路径 教学难点：一个顶点到其它顶点间的最短路径及任意两 顶点间的最短路径 授课内容： 一﹑从某个源点到其它各顶点间的最短路径 这里路径指两顶点间的通路，路径的长度指所有经过的边的总长。“最短路径”的问题指当两个顶点间通路多于一条时，如何找出边长总和为最短的那条。Dijkstra提出按路径长度递增的次序求最短路径的方法。 1.Dijkstra 求最短路径的基本思想 把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v1到其它各顶点间的最短路径,则在任意时刻，从v1到第一组各顶点间的最短路径都不大于从v1到第二组各顶点间的最短路径。 2.Dijkstra 求最短路径的步骤(1) 设图以邻接矩阵arcs存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权值用无穷大表示。从顶点v1到其它各顶点间的最短路径的具体步骤如下： 初始化：第一组（集合s）只含顶点v1,第二组（集合t）含有图中其余顶点。设一dist向量，其下标是各顶点，元素值是顶点v1到各顶点的边的权值。若v1到某顶点无边，dist向量中的对应值为无穷大。 2.Dijkstra 求最短路径的步骤(2) 选dist中最小的权值，将其顶点（j）加入s集合。 s=s{j} 修改从顶点v1到集合t(t=V-s)中各顶点的最短路径长度,如果 dist[j]+arcs[j][k]dist[k] 则修改dist[k]为 dist[k]=dist[j]+arcs[j][k] 重复（2）、（3）n-1次。由此求得v1到图上其余各顶点得最短路径。 3.Dijkstra 求最短路径的实例模拟(1) 3.Dijkstra 求最短路径的实例模拟(2) 4.Dijkstra 求最短路径的算法(1) void ShortestPath_DIJ(MGraph G,int v0,PathMatrix P,ShortPathTable D) {for (v=0;vG,vexnum;++v) {final[v]=FALSE; D[v]=G.arcs[v0][v]; for (w=0;wG,vexnum;++w) P[v][w]=FALSE; if (D[v]INFINITY){p[v][v0]=TRUE;P[v][v]=TRUE;} } D[v0]=0; final[v0]=TRUE; for (i=0;iG,vexnum;++i) {min=INFINITY; 4.Dijkstra 求最短路径的算法(2) for (w=0;wG,vexnum;++w) if(!final[w]) if(D[w]min) {v=w; min=D[w];} final[v]=TRUE; for (w=0;wG,vexnum;++w) if(!final[w] (min+G.arcs[v][w]D[w])) {D[w]=min+G.arcs[v][w]; P[w]=P[v]; P[w][w]=TRUE; } } } 5.Dijkstra 求最短路径的算法分析 对于n个顶点的图，求一个顶点到其余顶点的最短路径，循环n-1次，加上修改最短路径的循环，是二层循环，故时间复杂度为O(n2)。若只求从源点到某一顶点间的最短路径，和求到其余顶点间的最短路径相同，时间复杂度也是O(n2)。 二﹑每一对顶点间的最短路径 对于n个顶点的图，求每一对顶点间的最短路径，方法有： 按Dijkstra算法，求每一个顶点到其它各顶点间的最短路径，即是在上面基础上，再加一层循环，时间复杂度是O(n3)， 另一种方法是弗洛伊德（floyd）提出来的，时间复杂度也是O(n3)，但形式上简单。 1、弗洛伊德（floyd）算法的基本思想设求顶点vi到vj间的最短路径，若vi到vj有弧，则弧上的权 值是一条路径，但未必是最短路径，要经过n-1次测试。 首先将顶点v1加入，即看(vi,v1),(v1,vj)是否有路径，且比(vi,vj)低，如是，则用后两段路径代替，并称这是vi到vj中间顶点序号不大于1的最短路径。 再将顶点v2加入，得到vi到vj中间顶点序号不大于2的最短路径。 如此下去，直到vn加入，得到vi到vj中间