Mujin Blog

主题

00:00:00
2025-09-16 14:34:402025-11-29 02:24:23
4304
18.7m
0

图的拓扑排序和关键路径 原创 ​

一、AOV网(Activity On Vertex Network) ​

1.1 定义 ​

 AOV 网是一种（DAG，Directed Acyclic Graph）用，用有向的。 它是一种用有向图来描述工程或系统各子任务（活动）之间优先关系的有力工具。

  • 顶点（Vertex）：表示一个活动（Activity）或子任务。例如：课程教学中的“先修课程”，产品生产中的“组装零件”。
  • 有向边（Edge）：表示活动之间的或。若存在有向边 <i, j>，则表示活动 i 必须完成后，活动 j 才能开始。此时称 i 是 j 的直接前驱，j 是 i 的直接后继。

1.2 核心特性 ​

  1. 有向性：边有方向，表示。
  2. 无环性：AOV网中。如果存在环，则意味着某项活动必须以自身的完成为先决条件，这在逻辑上是荒谬的，工程也无法进行。

1.3 拓扑排序（Topological Sort） - AOV网的核心算法 ​

 拓扑排序是解决AOV网问题的核心算法，其目的是将AOV网中的所有顶点排成一个线性序列，使得任何一对顶点 u 和 v，若 <u, v> 是网中的边（即 u 领先于 v），则在序列中 u 也必须排在 v 的前面。

1.3.1 拓扑排序的算法步骤（常考过程描述）： ​

  1. 初始化：从AOV网中选择一个（即）的顶点并输出。
  2. 删除顶点及以其为尾的弧：从网中和所有（即将其直接后继顶点的入度减1）。
  3. 重复执行：重复上述两步，直到：
    • 当前网中（说明图中还有未输出的顶点，但已找不到入度为0的点，意味着图中）。
    • 或所有的顶点均已输出，得到一个拓扑序列。
  4. 拓扑排序示意图：对于图中(a)所示的有向无环图进行拓扑排序,得到的拓扑序列为: 6、1、4、3、2、5

拓扑排序示意图.webp

  1. 拓扑排序序列不唯一：拓扑排序的序列不唯一，存在多个入度为 0 的顶点时，根据选择的不同可能会出现多个拓扑序列，例：示意图中可能得到的序列还有： 1、6、4、3、2、5

二、AOE网 (Activity On Edge) ​

2.1 定义 ​

AOE网（Activity On Edge Network），即边表示活动的网络。它是一种用于估算项目工期的带权有向无环图（DAG）。

  • 顶点（Vertex）：表示事件（Event），即某个时刻或状态，例如“某项活动开始”或“某项活动结束”。顶点不消耗时间。
  • 有向边（Edge）：表示活动（Activity），即一个子任务或工序。边有，表示完成该活动所需的。
  • 源点与汇点：AOE网中，称为源点（Source），；，称为汇点（Sink），。

2.2 AOE网要研究的问题 ​

  1. 完成整个工程至少需要多少时间？
  2. 哪些活动是影响工程进度的？如何找到它们？

2.3 关键路径（Critical Path）法 ​

关键路径法是求解AOE网问题的核心算法。关键路径是从源点到汇点的（不是最短路径！），其长度决定了整个工程的最短工期。路径上的活动称为关键活动。

2.3.1 关键路径算法的核心参数 ​

为了找到关键路径，需要为每个事件（顶点）和每个活动（边）定义4个关键参数：

符号名称定义
ve(j)事件最早发生时间从源点到顶点 j 的最长路径长度。决定了以该事件为始点的活动的最早开始时间。
vl(j)事件最晚发生时间在不拖延整个工期的前提下，该事件最迟必须发生的时间。
e(i)活动最早开始时间该活动弧尾事件（起点） 的最早发生时间，即 e(i) = ve(j)。
l(i)活动最晚开始时间该活动弧头事件（终点） 的最晚发生时间减去活动持续时间，即 l(i) = vl(k) - dut(<j,k>)。
l(i)-e(i)活动时间余量该活动可以拖延的时间。如果时间余量为0，则该活动为关键活动。

2.3.2 算法步骤（非常重要！） ​

  1. 正向计算事件最早发生时间 ve(j) (从源点走向汇点)

    • ve(源点) = 0
    • ve(j) = Max{ ve(i) + dut(<i, j>) } （i 是 j 的所有前驱顶点）
    • 计算顺序：按拓扑排序的顺序推进。

  2. 反向计算事件最晚发生时间 vl(i) (从汇点倒推向源点)

    • vl(汇点) = ve(汇点)
    • vl(i) = Min{ vl(j) - dut(<i, j>) } （j 是 i 的所有后继顶点）
    • 计算顺序：按逆拓扑排序的顺序推进。

  3. 计算活动的最早/最晚开始时间 e(k) 和 l(k)

    • 设活动 k 用边 <i, j> 表示，其持续时间为 dut。
    • e(k) = ve(i) （活动最早开始时间 = 其起点事件的最早时间）
    • l(k) = vl(j) - dut （活动最晚开始时间 = 其终点事件的最晚时间 - 活动耗时）

  4. 确定关键活动和关键路径

    • 找出所有 l(k) == e(k) 的活动，这些就是关键活动。
    • 由关键活动首尾连接形成的从源点到汇点的路径，就是关键路径。

2.3.3 经典示例与手工计算（软考大题形式） ​

假设有一个AOE网，其结构如下所示。我们将一步步计算其关键路径。

AOE网结构（活动及其持续时间）： 顶点1为源点，顶点9为汇点。

计算事件最早发生时间 ve(j)
从源点（事件 1）开始，按照拓扑顺序计算：

  • ve(1) = 0
  • ve(2) = ve(1) + 6 = 6
  • ve(3) = ve(1) + 4 = 4
  • ve(4) = ve(1) + 5 = 5
  • ve(5) = max{ve(2)+1, ve(3)+1} = max{7, 5} = 7
  • ve(6) = ve(4) + 2 = 7
  • ve(7) = ve(5) + 9 = 16
  • ve(8) = max{ve(5)+7, ve(6)+4} = max{14, 11} = 14
  • ve(9) = max{ve(7)+2, ve(8)+4} = max{18, 18} = 18

计算事件最晚发生时间 vl(j)
从汇点（事件 9）开始，按照逆拓扑顺序计算：

  • vl(9) = ve(9) = 18
  • vl(8) = vl(9) - 4 = 14
  • vl(7) = vl(9) - 2 = 16
  • vl(6) = vl(8) - 4 = 10
  • vl(5) = min{vl(7)-9, vl(8)-7} = min{7, 7} = 7
  • vl(4) = vl(6) - 2 = 8
  • vl(3) = vl(5) - 1 = 6
  • vl(2) = vl(5) - 1 = 6
  • vl(1) = min{vl(2)-6, vl(3)-4, vl(4)-5} = min{0, 2, 3} = 0

计算活动的最早开始时间 e(i) 和最晚开始时间 l(i)
对于每个活动，计算其时间余量（l(i) - e(i)）：

  • a1: e = ve(1) = 0, l = vl(2)-6 = 0, 余量 = 0
  • a2: e = ve(1) = 0, l = vl(3)-4 = 2, 余量 = 2
  • a3: e = ve(1) = 0, l = vl(4)-5 = 3, 余量 = 3
  • a4: e = ve(2) = 6, l = vl(5)-1 = 6, 余量 = 0
  • a5: e = ve(3) = 4, l = vl(5)-1 = 6, 余量 = 2
  • a6: e = ve(4) = 5, l = vl(6)-2 = 8, 余量 = 3
  • a7: e = ve(5) = 7, l = vl(7)-9 = 7, 余量 = 0
  • a8: e = ve(5) = 7, l = vl(8)-7 = 7, 余量 = 0
  • a9: e = ve(6) = 7, l = vl(8)-4 = 10, 余量 = 3
  • a10: e = ve(7) = 16, l = vl(9)-2 = 16, 余量 = 0
  • a11: e = ve(8) = 14, l = vl(9)-4 = 14, 余量 = 0

计算过程用表格表示：

事件ve (最早)vl (最晚)活动e (最早)l (最晚)l - e关键活动
100a1000Yes
266a2022
346a3033
458a4660Yes
577a5462
6710a6583
71616a7770Yes
81414a8770Yes
91818a97103
a1016160Yes
a1114140Yes

确定关键活动和关键路径
时间余量为 0 的活动是关键活动：a1, a4, a7, a8, a10, a11

关键路径有两条：

  1. 1 → 2 → 5 → 7 → 9 (a1 → a4 → a7 → a10)
  2. 1 → 2 → 5 → 8 → 9 (a1 → a4 → a8 → a11)

总工期为 18 个单位时间。

总工期

总工期由从（顶点1）（顶点9）的（即）的决定。

三、AOE网 vs. AOV网（对比记忆） ​

特性AOV网 (Activity On Vertex)AOE网 (Activity On Edge)
顶点表示活动事件（状态、时刻）
边表示优先关系（无权）活动（有权，表时间）
关注点活动的先后顺序（拓扑排序）工程的最短工期（关键路径）
核心算法拓扑排序关键路径法（CPM）
应用课程先修关系、任务调度依赖项目工期估算、关键任务识别

四、最短路径 ​

在（或称）中，寻找两个顶点之间的那条路径，就是。

  • 路径长度：路径上所有边的权值之和。
  • 最短路径：所有可能路径中长度的那一条（注意：不是边数最少，而是）。
  • 源点（Source）：路径的起始顶点。
  • 终点（Destination）：路径的结束顶点。

根据问题范围，分为两类：

  1. 单源最短路径：求从一个到图中的最短路径。
  2. 多源最短路径：求图中之间的最短路径。

4.1 单源最短路径 ​

单源最短路径主要采用,是典型的策略

4.1.1 算法特点与使用场景 ​

  • 使用场景：等所有需要求。
  • 前提要求：图中（>=0）。这是该算法能正确工作的前提。
  • 算法思想：设置一个顶点集合 ，存放。每次从剩余顶点中选择一个离源点最近的顶点加入 ，并松弛其邻接边， 。

4.1.2 示例图与分步解题 ​

我们以下面的带权有向图为例，求从源点 A 到其他各顶点的最短路径。

邻接矩阵

算法步骤（使用三个数组：S, dist, path）：

  1. 初始化：

    • S[]（已确定集合）：{A}
    • dist[]（最短距离）：
      • dist[A] = 0
      • dist[B] = 10 (A→B)
      • dist[C] = 5 (A→C)
      • dist[D] = ∞ (暂无路径)
    • path[]（前驱顶点）：
      • path[B] = A
      • path[C] = A
      • path[D] = - (未知)
    顶点distpathS
    A0-✅
    B10A
    C5A
    D∞-

  2. 第一轮迭代：

    • 从 V-S (B, C, D) 中选出 dist 最小的顶点 C (dist[C]=5)。
    • 将 C 加入 S。
    • 松弛操作：检查 C 的所有邻接点 (B, D)。
      • 对于 B：dist[C] + weight(C,B) = 5 + 3 = 8。8 < 10 (当前dist[B])，所以 dist[B] = 8, path[B] = C。
      • 对于 D：dist[C] + weight(C,D) = 5 + 9 = 14。14 < ∞，所以 dist[D] = 14, path[D] = C。
    顶点distpathS
    A0-✅
    B8C
    C5A✅
    D14C

  3. 第二轮迭代：

    • 从 V-S (B, D) 中选出 dist 最小的顶点 B (dist[B]=8)。
    • 将 B 加入 S。
    • 松弛操作：检查 B 的所有邻接点 (D)。
      • 对于 D：dist[B] + weight(B,D) = 8 + 1 = 9。9 < 14 (当前dist[D])，所以 dist[D] = 9, path[D] = B。
    顶点distpathS
    A0-✅
    B8C✅
    C5A✅
    D9B

  4. 第三轮迭代：

    • 将最后一个顶点 D 加入 S。无需松弛操作。
    顶点distpathS
    A0-✅
    B8C✅
    C5A✅
    D9B✅

  5. 最终结果：

    • A->B：A->C->B，长度 8
    • A->C：A->C，长度 5
    • A->D：A->C->B->D，长度 9

  6. 路径还原技巧：从终点 D 的 path[D]=B 开始，找 B 的前驱 path[B]=C，再找 C 的前驱 path[C]=A，反向得到路径 A->C->B->D。

4.2 多源最短路径 ​

 一般采用，是典型的的策略。

4.2.1 算法特点与使用场景 ​

  • 使用场景：需要计算的场景，如计算。
  • 前提要求：可以处理，但的图（因为负权回路可以无限绕行，使路径长度无限小）。
  • 算法思想：对于任意两点 (i, j)，考虑所有其他顶点 k 作为中间点，检查是否存在一条经过 k 的路径比已知路径更短。

4.2.2 示例图与分步解题 ​

我们使用一个更简单的图来演示 算法的矩阵迭代过程。

算法步骤（使用距离矩阵 D）：

  1. 初始化距离矩阵 (即邻接矩阵)：

    ABC
    A0411
    B602
    C3∞0

  2. 第一轮迭代 (，允许借助顶点 中转)：

    • 检查所有 i->j，看 i->A->j 是否更短。
    • D[B][C]：min( D[B][C]=2, D[B][A]+D[A][C]=6+11=17 ) -> 2
    • D[C][B]：min( D[C][B]=∞, D[C][A]+D[A][B]=3+4=7 ) -> 7
    ABC
    A0411
    B602
    C370

  3. 第二轮迭代 (，允许借助顶点 , 中转)：

    • 检查所有 i->j，看 i->B->j 是否更短。
    • D[A][C]：min( D[A][C]=11, D[A][B]+D[B][C]=4+2=6 ) -> 6
    • D[C][A]：min( D[C][A]=3, D[C][B]+D[B][A]=7+6=13 ) -> 3
    ABC
    A046
    B602
    C370

  4. 第三轮迭代 (，允许借助顶点 , , 中转)：

    • 检查所有 i->j，看 i->C->j 是否更短。
    • D[B][A]：min( D[B][A]=6, D[B][C]+D[C][A]=2+3=5 ) -> 5
    • D[A][B]：min( D[A][B]=4, D[A][C]+D[C][B]=6+7=13 ) -> 4

    最终距离矩阵 ：

    ABC
    A046
    B502
    C370

结论：从上表可知：

  • A 到 C 的最短路径长度为 6 (路径: A->B->C)
  • B 到 A 的最短路径长度为 5 (路径: B->C->A)
  • C 到 B 的最短路径长度为 7 (路径: C->A->B)

4.3 总结与对比 ​

特性Dijkstra (迪杰斯特拉)Floyd (弗洛伊德)
解决问题单源最短路径多源最短路径（任意两点）
算法思想贪心算法动态规划
图的要求边权值非负可处理负权边，不能有负权回路
时间复杂度
空间复杂度
常见考查形式手工模拟计算过程，填写 dist[] 和 path[] 数组手工模拟矩阵迭代过程，填写距离矩阵 D[][]

应试技巧与常见陷阱：

  1. 算法。这是最常考的陷阱！
  2. 在手工模拟 Dijkstra 算法时，一旦一个顶点被加入集合 ，。
  3. Floyd 算法的（中间点 k 从 0 到 n-1），每次更新整个矩阵。
  4. 下午大题中，很可能会给一个简单的图，让你手工执行一遍两种算法的步骤，并写出结果。务必清晰展示每一步的中间结果。
最近更新