《数据结构-最短路径ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构-最短路径ppt课件.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构（数据结构（C版）版）清华大学出版社清华大学出版社专题专题3：最短路径：最短路径123最短路径的定义最短路径的定义 Dijkstra算法算法 Floyd算法算法 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社在非网图中在非网图中，最短路径是指两顶点之间经历的，最短路径是指两顶点之间经历的边数边数最少的路径。最少的路径。 6.4 最短路径最短路径最短路径最短路径 BAEDCAE：1ADE：2 ADCE：3ABCE：3数据结构（数据结构（C版）版）清华大学出版社清华大学出版社最短路径最短路径 在网图中在网图中，最短路径，最短路径是指两顶点之间经历的是指两顶点之间经历的边上权边上
2、权值之和值之和最短的路径。最短的路径。 BAEDC105030101002060AE：100ADE：90 ADCE：60 ABCE：706.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社问题描述：问题描述：给定带权有向图给定带权有向图G(V, E)和源点和源点vV，求从求从v到到G中其余各顶点的最短路径。中其余各顶点的最短路径。 单源点最短路径问题单源点最短路径问题 应用实例应用实例计算机网络传输的问题：怎样找到一种计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。发送一条
3、消息。迪杰斯特拉（迪杰斯特拉（Dijkstra）提出了一个按路径长度递增）提出了一个按路径长度递增的次序产生最短路径的算法的次序产生最短路径的算法Dijkstra算法。算法。6.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社基本思想基本思想：设置一个集合：设置一个集合S存放已经找到最短路径的顶点，存放已经找到最短路径的顶点，S的初始状态只包含源点的初始状态只包含源点v，对，对viV- -S，假设从源点假设从源点v到到vi的有的有向边为最短路径。以后每求得一条最短路径向边为最短路径。以后每求得一条最短路径v, , vk，就将就将vk加入集合加入集合S中，并将路径中
4、，并将路径v, , vk , vi与原来的假设相比较，取与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合路径长度较小者为最短路径。重复上述过程，直到集合V中中全部顶点加入到集合全部顶点加入到集合S中。中。Dijkstra算法算法6.4 最短路径最短路径 集集 合合 V- -S集集合合 Svkvvi数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Dijkstra算法算法伪代码伪代码6.4 最短路径最短路径设源点设源点v，w表示从顶点表示从顶点v到顶点到顶点vj的权值，的权值，dist(v, vj)表表示从顶点示从顶点v到顶点到顶点vj的最短路径长度，的最短路径长度
5、，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；数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABAEDC105030101002060S=AAB:(A, B)10AC:(A, C)AD: (A,
6、D)30AE: (A, E)100Dijkstra算法算法6.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABAEDC105030101002060S=A, BAB:(A, B)10AC:(A, B, C)60AD: (A, D)30AE: (A, E)100BDijkstra算法算法6.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABAEDC105030101002060S=A, B, DAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, E)90BDDijkstra算法算法6.4
7、 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABAEDC105030101002060S=A, B, D, CAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E)60BDCDijkstra算法算法6.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABAEDC105030101002060Dijkstra算法算法S=A, B, D, C, EAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E)60BDCE6.4 最短路径最短路
8、径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社p图的存储结构：图的存储结构：带权的邻接矩阵存储结构带权的邻接矩阵存储结构 p数组数组distn：每个分量每个分量disti表示当前所找到的从表示当前所找到的从始点始点v到终点到终点vi的最短路径的长度。初态为：若从的最短路径的长度。初态为：若从v到到vi有弧，则有弧，则disti为弧上权值；否则置为弧上权值；否则置disti为为。p数组数组sn：存放源点和已经生成的终点，其初态为存放源点和已经生成的终点，其初态为只有一个源点只有一个源点v。 数据结构数据结构 :6.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华
9、大学出版社1. 初始化数组初始化数组dist和和s；2. while ( (s中的元素个数中的元素个数n) ) 2.1 在在distn中求最小值，其下标为中求最小值，其下标为k； 2.2 输出输出distk； 2.3 修改数组修改数组dist； 2.4 将顶点将顶点vk添加到数组添加到数组s中；中；Dijkstra算法算法伪代码伪代码6.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Dijkstra算法算法伪代码伪代码6.4 最短路径最短路径ABEDC105030101002060数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Dijkstra算法算法
10、C+描述描述6.4 最短路径最短路径void Dijkstra(MGraph G, int v) for (i = 0; i G.vertexNum; i+) /初始化数组初始化数组distn disti = G.arcvi; s0 = v; distv = 0; /初始化集合初始化集合S，标记顶点，标记顶点v为源点为源点 num = 1; while (num G.vertexNum) /当顶点数当顶点数num小于图的顶点数小于图的顶点数 for (k = 0, i = 0; i G.vertexNum; i+) /在在dist中查找最小值元素中查找最小值元素 if (disti != 0)
11、 & (disti distk) k = i; coutdistk; snum+ = k; /将新生成的终点加入集合将新生成的终点加入集合S distk = 0; /置顶点置顶点k为已生成终点标记为已生成终点标记 for (i = 0; i distk + G.arcki) disti = distk + G.arcki; 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Dijkstra算法算法C+描述描述6.4 最短路径最短路径void Dijkstra(MGraph G, int v) for (i = 0; i G.vertexNum; i+) disti = G.arcvi;
12、 s0 = v; distv = 0; num = 1; while (num G.vertexNum) for (k = 0, i = 0; i G.vertexNum; i+) if (disti != 0) & (disti distk) k = i; coutdistk; snum+ = k; distk = 0; for (i = 0; i distk + G.arcki) disti = distk + G.arcki; 时间复杂度？时间复杂度？O(n)O(n)O(n)O(n)因此，时间复杂度是因此，时间复杂度是O(n2)。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社
13、6.4 最短路径最短路径p数组数组pathn：pathi是一个字符串，表示当前所找是一个字符串，表示当前所找到的从始点到的从始点v到终点到终点vi的最短路径。初态为：若从的最短路径。初态为：若从v到到vi有弧，则有弧，则pathi为为vvi；否则置否则置pathi空串。每次迭空串。每次迭代依据下式进行修改：代依据下式进行修改：如何修改存储结构，使得在求得最短路径长如何修改存储结构，使得在求得最短路径长度的同时求得最短路径？度的同时求得最短路径？if (disti distk + G.arcki) pathi = pathk + G.vertexi Dijkstra算法算法C+描述描述数据结构（
14、数据结构（C版）版）清华大学出版社清华大学出版社每一对顶点之间的最短路径每一对顶点之间的最短路径 问题描述问题描述：给定带权有向图：给定带权有向图G(V, E)，对任意顶点对任意顶点vi, ,vjV（ij），求顶点），求顶点vi到顶点到顶点vj的最短路径。的最短路径。 p 解决办法解决办法1：每次以一个顶点为源点调用：每次以一个顶点为源点调用Dijkstra算法。显然，时间复杂度为算法。显然，时间复杂度为O(n3)。p 解决办法解决办法2：弗洛伊德提出的求每一对顶点之间：弗洛伊德提出的求每一对顶点之间的最短路径算法的最短路径算法Floyd算法，其时间复杂度也是算法，其时间复杂度也是O(n3)，
15、但形式上要简单些。，但形式上要简单些。6.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社基本思想基本思想：对于从：对于从vi到到vj的弧，的弧，进行进行n次试探：次试探：首先首先考虑路径考虑路径vi, ,v0, ,vj是否存在，如果存在，则比较是否存在，如果存在，则比较vi, ,vj和和vi, ,v0, ,vj的路径长度，取较短者为从的路径长度，取较短者为从vi到到vj的中间顶的中间顶点的序号点的序号不大于不大于0的最短路径。在路径上再增加一个的最短路径。在路径上再增加一个顶点顶点v1，依依此类推，此类推，在经过在经过n次比较后，最后求得的次比较后，最后求得的必
16、是从顶点必是从顶点vi到顶点到顶点vj的最短路径。的最短路径。 Floyd算法算法6.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社0 4 116 0 23 0有向网图有向网图 邻接矩阵邻接矩阵Floyd算法算法acb3461126.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Floyd算法算法acb346112dist-1 =0 4 116 0 23 0path-1 = ab ac ba bc ca 初始化初始化6.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Floyd算法算法acb34611
17、2dist-1 =0 4 116 0 23 0path-1 = ab ac ba bc ca 第第1次迭代次迭代dist0 =0 4 116 0 23 7 0path0 = ab ac ba bc ca cab 6.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Floyd算法算法acb346112第第2次迭代次迭代dist0 =0 4 116 0 23 7 0path0 = ab ac ba bc ca cab dist1 =0 4 66 0 23 7 0path1 = ab abc ba bc ca cab 6.4 最短路径最短路径数据结构（数据结构（C版）版
18、）清华大学出版社清华大学出版社Floyd算法算法acb346112第第3次迭代次迭代dist2 =0 4 65 0 23 7 0path2 = ab abc bca bc ca cab dist1 =0 4 66 0 23 7 0path1 = ab abc ba bc ca cab 6.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 图的存储结构图的存储结构：带权的邻接矩阵存储结构：带权的邻接矩阵存储结构 数组数组distnn：存放在迭代过程中求得的最短路：存放在迭代过程中求得的最短路径长度。迭代公式：径长度。迭代公式： 数组数组pathnn：存放从存放从vi
19、到到vj的最短路径，初始的最短路径，初始为为pathij=vivj。数据结构数据结构dist-1ij=arcijdist kij=mindistk-1ij, distk-1ik+distk-1kj 0k n-16.4 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社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(n2)O(n3)因此，时间复杂度是因此，时间复杂度是O(n3)。