数据结构最短路径剖析.ppt

数据结构（C＋＋版） 清华大学出版社 专题3：最短路径 1 2 3 最短路径的定义 Dijkstra算法 Floyd算法 在非网图中，最短路径是指两顶点之间经历的边数最少的路径。 6.4 最短路径 最短路径 B A E D C AE：1 ADE：2 ADCE：3 ABCE：3 最短路径 在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。 B A E D C 10 50 30 10 100 20 60 AE：100 ADE：90 ADCE：60 ABCE：70 6.4 最短路径 问题描述：给定带权有向图G＝(V, E)和源点v∈V，求从v到G中其余各顶点的最短路径。 单源点最短路径问题 应用实例——计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。 迪杰斯特拉（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 集 合 S vk v vi Dijkstra算法——伪代码 6.4 最短路径 设源点v，wv, vj表示从顶点v到顶点vj的权值，dist(v, vj)表示从顶点v到顶点vj的最短路径长度，Dijkstra算法的基本思想用伪代码描述如下： 1. 初始化：集合S = {v}；dist(v, vj) = wv, vj, (j=1..n)； 2. 重复下述操作直到S == V 2.1 dist(v, vk) = min{dist(v, vj), (j=1..n)}； 2.2 S = S + {vk}； 2.3 dist(v, vj)=min{dist(v, vj), dist(v, vk) + wvk, vj}； A B A E D C 10 50 30 10 100 20 60 S={A} A→B:(A, B)10 A→C:(A, C)∞ A→D: (A, D)30 A→E: (A, E)100 Dijkstra算法 6.4 最短路径 A B A E D C 10 50 30 10 100 20 60 S={A, B} A→B:(A, B)10 A→C:(A, B, C)60 A→D: (A, D)30 A→E: (A, E)100 B Dijkstra算法 6.4 最短路径 A B A E D C 10 50 30 10 100 20 60 S={A, B, D} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, E)90 B D Dijkstra算法 6.4 最短路径 A B A E D C 10 50 30 10 100 20 60 S={A, B, D, C} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, C, E)60 B D C Dijkstra算法 6.4 最短路径 A B A E D C 10 50 30 10 100 20 60 Dijkstra算法 S={A, B, D, C, E} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, C, E)60 B D C E 6.4 最短路径 图的存储结构：带权的邻接矩阵存储结构 数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。 数组s[n]：存放源点和已经生成的终点，其初态为只有一个源点v。 数据结构 : 6.4 最短路径 1. 初始化数组dist和s； 2. while (s中的元素个数n) 2.1 在dist[n]中求最小值，其下标为k； 2.2 输出dist[k]； 2.3 修改数组dist； 2.4 将顶点vk添加到数组s中； Dijkstra算法——伪代码 6.4 最短路径 Dijkstra算法——伪代码 6.4 最短路径 A B E D C 10 5