数据结构-最短路径.ppt

《数据结构-最短路径.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、专题3：最短路径123最短路径的定义Dijkstra算法Floyd算法在非网图中，最短路径是指两顶点之间经历的边数最少的路径。6.4最短路径最短路径BAEDCAE：1ADE：2ADCE：3ABCE：3最短路径在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。BAEDC105030101002060AE：100ADE：90ADCE：60ABCE：706.4最短路径问题描述：给定带权有向图G＝(V,E)和源点v∈V，求从v到G中其余各顶点的最短路径。单源点最短路径问题应用实例——计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。

2、迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法——Dijkstra算法。6.4最短路径基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v,…,vk，就将vk加入集合S中，并将路径v,…,vk,vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。Dijkstra算法6.4最短路径集合V-S集合SvkvviDijkstra算法——伪代码6.4最短路径设源点v，w表示从顶点v到顶点vj的权

3、值，dist(v,vj)表示从顶点v到顶点vj的最短路径长度，Dijkstra算法的基本思想用伪代码描述如下：1.初始化：集合S={v}；dist(v,vj)=w,(j=1..n)；2.重复下述操作直到S==V2.1dist(v,vk)=min{dist(v,vj),(j=1..n)}；2.2S=S+{vk}；2.3dist(v,vj)=min{dist(v,vj),dist(v,vk)+w}；ABAEDC105030101002060S={A}A→B:(A,B)10A→C:(A,C)∞A→D:(A,D)30A→E:(A,E)100Dijkstra算法6

4、.4最短路径ABAEDC105030101002060S={A,B}A→B:(A,B)10A→C:(A,B,C)60A→D:(A,D)30A→E:(A,E)100BDijkstra算法6.4最短路径ABAEDC105030101002060S={A,B,D}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,E)90BDDijkstra算法6.4最短路径ABAEDC105030101002060S={A,B,D,C}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60BDCDijkstra算法6.

5、4最短路径ABAEDC105030101002060Dijkstra算法S={A,B,D,C,E}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60BDCE6.4最短路径图的存储结构：带权的邻接矩阵存储结构数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。数组s[n]：存放源点和已经生成的终点，其初态为只有一个源点v。数据结构:6.4最短路径1.初始化数组dist和s；2.while(s中的元素个数

6、1在dist[n]中求最小值，其下标为k；2.2输出dist[k]；2.3修改数组dist；2.4将顶点vk添加到数组s中；Dijkstra算法——伪代码6.4最短路径Dijkstra算法——伪代码6.4最短路径ABEDC105030101002060Dijkstra算法——C++描述6.4最短路径voidDijkstra(MGraphG,intv){for(i=0;i

7、exNum)//当顶点数num小于图的顶点数{for(k=0,i=0;idist[k]+G.arc[k][i])dist[