文档介绍：*第十九讲最短路径**教材与参考资料普通高等教育“十一五”国家级规划教材普通高等教育精品教材《算法与数据结构—C语言描述》(第2版)张乃孝编著,()普通高等教育“十一五”国家级规划教材配套参考书《算法与数据结构》(第2版)学****指导与****题解析张乃孝编著,高等教育出版社2009.**,则称这两个顶点间存在一条路径。从一个顶点到另一个顶点间可能存在多条路径,而每条路径上经过的边数并不一定相同。如果图是一个带权图,则路径长度为路径上各边的权值的总和,两个顶点间路径长度最短的那条路径称为两个顶点间的最短路径,其路径长度称为最短路径长度。*。该算法假设所有边的权都大于等于零。*基本思想设置一个集合U,存放已求出最短路径的顶点,V-U是尚未确定最短路径的顶点集合。U的初始状态为{v0}。按路径长度递增的次序逐个产生vx的最短路径,把vx加入U中。直到U=V时终止。距离值V-U图GUv0vi1vi3vi2为每个顶点设置一个距离值(已知最短距离):集合U中某顶点的距离值就是从顶点v0到该顶点的最短路径长度;集合V-U中某顶点的距离值是从顶点v0到该顶点的只包括集合U中顶点为中间顶点的最短路径长度。性质:若vi是V-U中距离值最小的结点,那么这个距离值就是从v0到vi的最短路径。。**初始状态:集合U中只有顶点v0,顶点v0对应的距离值为0,集合V-U中顶点vi的距离值为边(v0,vi)(i=1,2,…,n-1)的权,如果v0和vi间无边直接相连,则vi的距离值为∞(实际程序中可以用一个足够大的数代替)。处理框架:(1)在集合V-U中选择距离值最小的顶点vmin加入集合U;(2)对集合V-U中各顶点的距离值进行修正:如果加入顶点vmin为中间顶点后,使v0到vi的距离值比原来的距离值更小,则修改vi的距离值。(3)重复(1)(2)操作,直到从v0出发可以到达的所有顶点都在集合U中为止。按路径长度递增的次序逐个产生最短路径例:已知带权图G10如下图所示及其邻接矩阵A,求从顶点v0到其它各顶点的最短路径úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥=03030350201502051504510500A45v050v15v41520v215v33v53520301045v050v15v41520v215v33v535203010[45][50][10][¥][¥]绿色为从U到V-U的边,选(v0,v2)把v2加入U*45v050v15v41520v215v33v535203010[¥][45][25][50]选(v2,v3),把v3加入U45v050v15v41520v215v33v535203010[45][45][¥]选(v3,v1),把v1加入U45v050v15v41520v215v33v535203010[¥][45]选(v0,v4),把v4加入U45v050v15v41520v215v33v535203010**图选择邻接矩阵表示法,其中关系矩阵的对角线初值均取0。算法中,将放入集合U中结点对应的关系矩阵中对角线元素值修改为1;另外设置一个数组dist,dist[i]用于存放v0到顶点vi的最短路径及其最短路径长度(计算过程中为距离值)∶ypedefstruct{ AdjTypelength; /*最短路径长度*/ intprevex; /*从v0到达vi(i=1,2,…n-1)的最短路径上vi的前趋顶点*/}Path;Path*dist;存储结构