数据结构Java版图3最短路径ppt课件.ppt

《数据结构Java版图3最短路径ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最短路径1最短路径问题提出问题如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小?问题解法边上权值非负情形的单源最短路径问题—Dijkstra算法2Dijkstra算法思想问题的提法：给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。为求得这些最短路径,Dijkstra提出按路径长度的递增次序,逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最

2、短路径全部求出为止3Dijkstra逐步求解的过程10432101003050206010源点终点最短路径路径长度v0v1(v0,v1)10v2(v0,v1,v2)(v0,v3,v2),60,50v3(v0,v3)30v4(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)100,90,604引入辅助数组dist。它的每一个分量dist[i]表示当前找到的从源点v0到终点vi的最短路径的长度。初始状态：若从源点v0到顶点vi有边,则dist[i]为该边上的权值；若从源点v0到顶点vi无边,则dist[i]为。假设S是已求得的最短

3、路径的终点的集合，则可证明：下一条最短路径必然是从v0出发，中间只经过S中的顶点便可到达的那些顶点vx(vxV-S)的路径中的一条。每次求得一条最短路径后,其终点vk加入集合S，然后对所有的viV-S，修改其dist[i]值。5Dijkstra算法设计①初始化：S←{v0};dist[j]←Edge[0][j],j=1,2,…,n-1;//n为图中顶点个数②求出最短路径的长度：dist[k]←min{dist[i]},iV-S;S←SU{k};③修改：dist[i]←min{dist[i],dist[k]+Edge[k][i]},对于

4、每一个iV-S;④判断：若S=V,则算法结束，否则转②。6Dijkstra算法中各辅助数组的最终结果从表中读取源点0到终点v的最短路径的方法:举顶点4为例path[4]=2path[2]=3path[3]=0，反过来排列，得到路径0,3,2,4，这就是源点0到终点4的最短路径。041231050102060301007程序运行结果8