数据结构A第9章(南邮)2014.ppt

9.7 单源最短路径 9.7 单源最短路径 9.7 单源最短路径 9.7 单源最短路径 9.7 单源最短路径 9.7 单源最短路径 9.7 单源最短路径 9.7 单源最短路径 9.7 单源最短路径 9.8 所有顶点之间的最短路径 9.8 所有顶点之间的最短路径 9.8 所有顶点之间的最短路径 9.8 所有顶点之间的最短路径 9.8 所有顶点之间的最短路径 9.8 所有顶点之间的最短路径 9.8 所有顶点之间的最短路径 9.8 所有顶点之间的最短路径 9.8 所有顶点之间的最短路径 9.8 所有顶点之间的最短路径 9.8 所有顶点之间的最短路径 9.8 所有顶点之间的最短路径 本章小结 9.6.1 单源最短路径 1.单源最短路径问题 给定带权的有向图G=(V,E)，源点v?V，求从顶点v到顶点集V中其余各顶点的最短路径。 2. Dijkstra算法 （１）算法思想： 首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有顶点之间的最短路径都已求得为止。 初始状态时，集合S中只有一个源点，设为顶点v0。首先产生从源点v0到它自身的路径，其长度为0，将v0加入S。 算法的每一步上，按照最短路径值的非递减次序，产生下一条最短路径，并将该路径的终点t?V-S加入S。 直到S＝V时算法结束。 把V分成两组： （1）S：存放已求得最短路径的顶点的集合 （2）V-S=T：尚未确定最短路径的顶点集合 迪杰斯特拉算法的具体步骤： 当前最短路径 在算法执行中，一个顶点t?V－S的当前最短路径，是一条从源点v0到顶点t的路径 （v0，…，u，t） 在该路径上，除顶点t 外，其余顶点的最短路径都已求得，即路径（v0，…，u）上所有顶点都属于S。 （v0，…，u，t）是所有这些路径中的最短者。 源点　　终点　　　最短路径　 　V0　　　　 V1 45 　　　　 V2 10 V3 25 V4 55 V5 ∞ 假设顶点２,３已求出最短路径。 顶点4的当前最短路径是： 路径（０,４）与路径（０,２,３,４）之间的较短者 3. Dijkstra算法用到的数据结构 (1) 图用邻接矩阵； (2)一维布尔数组s 若s[i]为true，表示顶点i在S中，否则表示i在V－S中。? (3) 一维数组d：保存各条最短路径的长度，其中，d[i]存放从源点v0到顶点vi的最短路径长度。在算法执行中，若vi是尚未产生最短路径的顶点，则d[i]被定义为“由已经产生的最短路径上再扩充一条边”所形成的从v0到vi的“当前最短路径”。 (4) 一维数组path：指示该条最短路径。 path[i]给出：从v0到vi的最短路径上，顶点vi前面的顶点。 例如:从v0到v1的最短路径为（v0,v2,v3,v1） 则有path[1]=3 9.7.5 算法的C++程序实现 （１）初始化 （1）s[v0]=true （2）d[i] （3）path[i]: 若v0,vi?E，则 path[i]=0， 否则 path[i]=-1 9.7.5 算法的C++程序实现 （２）求第一条最短路径 第一条最短路径是所有最短路径中的最短者，它必定只包含一条边(v0，k)，并满足： 例如： 9.7.5 算法的C++程序实现 （３）更新数组d和path 将顶点k加入S，并对所有的i∈V-S修正d的值，使d中始终是顶点i的当前最短路径长度。 例如 修改d的值 9.7.5 算法的C++程序实现 （４）求下一条最短路径 下一条最短路径的终点，必定是V－S中，具有最短的当前最短路径值的顶点k，满足 9.7.5 算法的C++程序实现 9.7.5 算法的C++程序实现 template class T int ExtMGraphT::Choose(int* d, bool* s) {//选出最小的d[i], i∈V-S int i,minpos; T min; min=INFTY; minpos=-1; for (i=1;in;i++) if (d[i]min !s[i]){ min=d[i];minpos=i; } return minpos; //返回下标位置 } 9.7.5 算法的C++程序实现 template class T void ExtMGr