数据机构课件第7章图2.ppt

二、每一对顶点之间的最短路径 方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次—— T(n)=O(n3) 方法二：弗洛伊德(Floyd)算法 算法思想：逐个顶点试探法 求最短路径步骤 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧Vi,Vj，则对应元素为权值；否则为∞ 逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值 所有顶点试探完毕，算法结束 Exercise 7 对如下 AOE 网，试给出： ⑴各活动的最早开始时间和最迟开始时间 ⑵该 AOE 网的关键路径 v1 v2 v3 v5 v4 v7 v8 v9 v6 v10 a1=8 a3=7 a2=6 a4=3 a5=10 a6=9 a7=9 a8=13 a9=2 a10=4 a11=19 a12=8 a13=6 a14=14 a15=10 7.6 最短路径 路径上的第一个顶点为源点 (Source)，最后一个顶点为终点 (Destination) 一、从某个源点到其余各顶点的最短路径 v5 v0 v4 v1 v3 v2 100 60 30 10 10 5 50 20 迪杰斯特拉 (Dijkstra) 提出按路径长度递增的次序产生最短路径的算法 引进一个辅助向量 D，每个分量 D[i] 表示当前所找到的从始点 v 到每个终点 vi的最短路径 v=v0 v5 v0 v4 v1 v3 v2 100 60 30 10 10 5 50 20 1 2 3 4 5 D ∞ 10 ∞ 30 100 长度为 D[j] = Min{D[i] | vi∈V} 的路径就是从 v 出发的长度最短的一条最短路径 (v，vj) 长度次短的路径的终点是 vk，那么这条路径只能是下列二者之一： (v，vk) (v，vj，vk) 假设 S 为已求得最短路径的终点的集合，则可证明：下一条最短路径 (设其终点为 x) 或者是弧 (v，x)，或者是中间只经过 S 中的顶点而最后到达顶点 x 的路径 假设 S 为已求得最短路径的终点的集合，则可证明：下一条最短路径 (设其终点为 x) 或者是弧 (v，x)，或者是中间只经过 S 中的顶点而最后到达顶点 x 的路径 证明：假设 v 到 x 的最短路径为 (v，…，y，…，x) 且此路径上有一个顶点 y 不在 S 中，则说明存在一条终点不在 S 而长度比 (v，…，y，…，x) 更短的路径 (v，…，y) 但是，这是不可能的。即假设不成立 下一条长度次短的最短路径的长度必是 D[j] = Min{D[i] | vi∈V – S} 其中，D[i] 或者是弧 (v，vi) 上的权值，或者是 D[k](vk∈S) 和弧 (vk，vi) 上的权值之和 设图以邻接矩阵arcs存储 矩阵中各元素的值为各边的权值 顶点间无边时其对应权值用无穷大表示。 Dijkstra 算法求最短路径的步骤 （1）初始化：第一组（集合s）只含顶点v1,第二组（集合t）含有图中其余顶点。设一dist向量，其下标是各顶点，元素值是顶点v1到各顶点的边的权值。若v1到某顶点无边，dist向量中的对应值为无穷大。 （2） 选dist中最小的权值，将其顶点（j）加入s集合。 s = s ∪ {j} （3）修改从顶点v1到集合t(t=V-s)中各顶点的最短路径长度, 如果 dist[j]+arcs[j][k]dist[k] 则修改dist[k]为 dist[k]=dist[j]+arcs[j][k] （4） 重复（2）、（3）n-1次。由此求得v1到图上其余各顶点得最短路径。 ???????? v5 v0 v4 v1 v3 v2 100 60 30 10 10 5 50 20 v0 v1 v2 v3 v4 v5 0 1 2 3 4 5 1 2 3 4 5 D ∞ 10 ∞ 30 100 ∞ 10 60 30 100 ∞ 10 50 30 90 ∞ 10 50 30 60 ∞ 10 50 30 60 Dijkstra 求最短路径的算法分析 对于n个顶点的图，求一个顶点到其余顶点的最短路径，循环n-1次， 加上修改最短路径的循环，是二层循环，故时间复杂度为O(n2)。 ???? Exercise 8 对如下有向网，用 Dijkstra 方法求从顶点 F 到图中其他顶点的最短路径，写出具体的执行过程 A B C D E F 10 10 15 8 10 4 4 2 15 20 * 7.5 有向无环图及其应用 一个无环