数据结构（Java语言描述）配套课件.ppt

怎样求单源点的最短路径呢? 2、迪杰斯特拉（Dijkstra）算法： 按路径长度递增次序产生各顶点的最短路径。 1、将源点到终点的所有路径都列出来， 然后在其中选最短的一条。 缺点：当路径特别多时，特别麻烦； 没有规律可循。 Dijkstra 算法：按路径长度递增次序产生最短路径 Dijkstra 算法步骤： 终点 从 v0 到各终点的最短路径及长度 i =1 i =2 i =3 i =4 i =5 i =6 v1 v2 v3 v4 v5 v6 vj S 13 8 ∞ 30 ∞ 32 v2 8 13 13 30 ∞ 32 v1 13 13 30 22 20 v3 8+5 19 22 20 v4 8+5+6 21 20 v6 13+7 21 v5 8+5 +6+2 v5 v1 v6 v4 v3 v2 v0 8 5 6 2 30 13 7 17 32 9 v2 v3 v1 v4 v5 v6 v0 4 2 3 0 1 10 100 60 60 50 10 30 终点 i =1 i =2 i =3 i =4 v1 v2 v3 v4 vj 从 v0 到各终点的最短路径及长度 dist[]数组记录最短距离 path[]数组路径中最后一个顶点 100 0 100 0 90 2 70 3 30 0 ∞ -1 10 0 30 0 60 4 60 4 v4 v2 v3 v1 练习：求从V0出发，到其它各顶点的最短路径。 6.5.2拓扑排序 有向图中，若以图中的顶点表示活动，以弧表示活动之间的优先关系，这样的有向图称为AOV网（Active On Vertex Network）。 1、若vi,vj是AOV网中的弧，则称vi是vj的直接前驱，vj是vi的直接后继。 2、在AOV网中，不应该出现有向环路。 每个活动之间有时存在一定的先决条件关系，即在时间上有着一定的相互制约的关系。 图6.24表示课程之间关系的AOV网 判断图中是否存在回路的方法是：拓扑排序 对AOV网进行拓扑排序的方法的步骤如下： (1)从有向图中选一个没有前驱的顶点，并输出之; (2)从有向图中删去此顶点以及所有以它为尾的弧; 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。 该图的拓扑序列有两个： （A，B，C，D） （A，C，B，D） 一个AOV网的拓扑排序序列是不唯一的。 (a) 无环AOV网 (b) 有环AOV网 找不到该网的拓扑有序序列 练习：对下面的有向图进行拓扑排序，写出所有的拓扑排序序列。 6.5.3关键路径 例：设一个工程有 11 项活 动， 9 个事件。 事件 v1 — 表示整个工程 开始（源点） 事件 v9 — 表示整个工程 结束（汇点） 把工程计划表示为有向图，用顶点表示事件，弧表示 活动，弧的权表示活动持续时间。每个事件表示在它之前 的活动已经完成，在它之后的活动可以开始。称这种有向 图为边表示活动的图，简称为 AOE (Activity On Edge) 网。 a8=7 a9=4 a10=2 a11=4 a7=9 a4=1 a5=1 a6=2 a2=4 a1=6 v9 v8 v7 v6 v4 v5 v3 v2 v1 a3=5 对AOE网，我们关心两个问题： (1) 完成整项工程至少需要 多少时间？ (2) 哪些活动是影响工程进 度的关键？ a8=7 a9=4 a10=2 a11=4 a7=9 a4=1 a5=1 a6=2 a2=4 a1=6 v9 v8 v7 v6 v4 v5 v3 v2 v1 a3=5 路径长度 — 路径上各活动持续时间之和。 关键路径 — 路径长度最长的路径。 ve(j) — 表示事件 vj 的最早发生时间。 vl(j) — 表示事件 vj 的最迟发生时间。 e(i) — 表示活动 ai 的最早开始时间。 l(i) — 表示活动 ai 的最迟开始时间。 l(i) - e(i) — 表示完成活动 ai 的时间余量。 关键活动 — 关键路径上的活动，即 l(i) = e(i) 的活动。 ve(3) = 4 vl(3) = 6 e(5) = 4 l(5) = 6 l(5) - e(5) = 2 如何找 l(i) = e(i) 的关键活动？ 设活动 ai 用弧 j, k 表示，其持续时间记为：dut(j, k) 则有： (1) e(i) = ve(j)