数据结构最短路径ppt课件.ppt

上传人:小飞机 文档编号:1350163 上传时间:2022-11-12 格式:PPT 页数:26 大小:197KB
返回 下载 相关 举报
数据结构最短路径ppt课件.ppt_第1页
第1页 / 共26页
数据结构最短路径ppt课件.ppt_第2页
第2页 / 共26页
数据结构最短路径ppt课件.ppt_第3页
第3页 / 共26页
数据结构最短路径ppt课件.ppt_第4页
第4页 / 共26页
数据结构最短路径ppt课件.ppt_第5页
第5页 / 共26页
点击查看更多>>
资源描述

《数据结构最短路径ppt课件.ppt》由会员分享,可在线阅读,更多相关《数据结构最短路径ppt课件.ppt(26页珍藏版)》请在三一办公上搜索。

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

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

3、长度,Dijkstra算法的基本思想用伪代码描述如下:,1. 初始化:集合S = v;dist(v, vj) = w, (j=1.n);2. 重复下述操作直到S = V 2.1 dist(v, vk) = mindist(v, vj), (j=1.n); 2.2 S = S + vk; 2.3 dist(v, vj)=mindist(v, vj), dist(v, vk) + w;,10,50,30,10,100,20,60,S=AAB:(A, B)10AC:(A, C)AD: (A, D)30AE: (A, E)100,Dijkstra算法,6.4 最短路径,10,50,30,10,100,

4、20,60,S=A, BAB:(A, B)10AC:(A, B, C)60AD: (A, D)30AE: (A, E)100,Dijkstra算法,6.4 最短路径,10,50,30,10,100,20,60,S=A, B, DAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, E)90,Dijkstra算法,6.4 最短路径,10,50,30,10,100,20,60,S=A, B, D, CAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E)60,Dijkstra算法,6.4 最短路径,10,

5、50,30,10,100,20,60,Dijkstra算法,S=A, B, D, C, EAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E)60,6.4 最短路径,图的存储结构:带权的邻接矩阵存储结构,数组distn:每个分量disti表示当前所找到的从始点v到终点vi的最短路径的长度。初态为:若从v到vi有弧,则disti为弧上权值;否则置disti为。,数组sn:存放源点和已经生成的终点,其初态为只有一个源点v。,数据结构 :,6.4 最短路径,1. 初始化数组dist和s;2. while (s中的元素个数n) 2.1 在distn

6、中求最小值,其下标为k; 2.2 输出distk; 2.3 修改数组dist; 2.4 将顶点vk添加到数组s中;,Dijkstra算法伪代码,6.4 最短路径,Dijkstra算法伪代码,6.4 最短路径,Dijkstra算法C+描述,6.4 最短路径,void Dijkstra(MGraph G, int v) for (i = 0; i distk + G.arcki) disti = distk + G.arcki; ,Dijkstra算法C+描述,6.4 最短路径,void Dijkstra(MGraph G, int v) for (i = 0; i distk + G.arcki

7、) disti = distk + G.arcki; ,时间复杂度?,因此,时间复杂度是O(n2)。,6.4 最短路径,数组pathn:pathi是一个字符串,表示当前所找到的从始点v到终点vi的最短路径。初态为:若从v到vi有弧,则pathi为vvi;否则置pathi空串。每次迭代依据下式进行修改:,如何修改存储结构,使得在求得最短路径长度的同时求得最短路径?,if (disti distk + G.arcki) pathi = pathk + G.vertexi,Dijkstra算法C+描述,每一对顶点之间的最短路径,问题描述:给定带权有向图G(V, E),对任意顶点vi,vjV(ij),

8、求顶点vi到顶点vj的最短路径。,解决办法1:每次以一个顶点为源点调用Dijkstra算法。显然,时间复杂度为O(n3)。 解决办法2:弗洛伊德提出的求每一对顶点之间的最短路径算法Floyd算法,其时间复杂度也是O(n3),但形式上要简单些。,6.4 最短路径,基本思想:对于从vi到vj的弧,进行n次试探:首先考虑路径vi,v0,vj是否存在,如果存在,则比较vi,vj和vi,v0,vj的路径长度,取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1,依此类推,在经过n次比较后,最后求得的必是从顶点vi到顶点vj的最短路径。,Floyd算法,6.4 最短路径,0

9、 4 116 0 23 0,有向网图 邻接矩阵,Floyd算法,3,4,6,11,2,6.4 最短路径,Floyd算法,dist-1 =,0 4 116 0 23 0,path-1 =,ab ac ba bc ca,初始化,6.4 最短路径,Floyd算法,dist-1 =,0 4 116 0 23 0,path-1 =,ab ac ba bc ca,第1次迭代,dist0 =,0 4 116 0 23 7 0,path0 =,ab ac ba bc ca cab,6.4 最短路径,Floyd算法,第2次迭代,dist0 =,0 4 116 0 23 7 0,path0 =,ab ac ba

10、bc ca cab,dist1 =,0 4 66 0 23 7 0,path1 =,ab abc ba bc ca cab,6.4 最短路径,Floyd算法,3,4,6,11,2,第3次迭代,dist2 =,0 4 65 0 23 7 0,path2 =,ab abc bca bc ca cab,dist1 =,0 4 66 0 23 7 0,path1 =,ab abc ba bc ca cab,6.4 最短路径,图的存储结构:带权的邻接矩阵存储结构 数组distnn:存放在迭代过程中求得的最短路径长度。迭代公式: 数组pathnn:存放从vi到vj的最短路径,初始为pathij=vivj。

11、,数据结构,6.4 最短路径,void Floyd(MGraph G) for (i=0; iG.vertexNum; i+) for (j=0; jG.vertexNum; j+) distij=G.arcij; if (distij!=) pathij=G.vertexi+G.vertexj; else pathij=; for (k=0; kG.vertexNum; k+) for (i=0; iG.vertexNum; i+) for (j=0; jG.vertexNum; j+) if (distik+distkjdistij) distij=distik+distkj; pathij=pathik+pathkj; ,Floyd算法C+描述,6.4 最短路径,时间复杂度?,因此,时间复杂度是O(n3)。,

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号