BFS（无权图）#

BFS 求无权图单源最短路径利用其逐层扩展的特性：首次到达即最短。详见 图的遍历。

Dijkstra 算法（非负权图）#

1
若 dist[u] + w(u,v) < dist[v]，则更新 dist[v] = dist[u] + w(u,v)

Floyd 算法（多源最短路径）#

1
dist(k)[i][j] = min(dist(k-1)[i][j], dist(k-1)[i][k] + dist(k-1)[k][j])

1
for (int k = 0; k < V; k++)        // k 必须在最外层
2
    for (int i = 0; i < V; i++)
3
        for (int j = 0; j < V; j++)
4
            if (dist[i][k] + dist[k][j] < dist[i][j])
5
                dist[i][j] = dist[i][k] + dist[k][j];

三种算法对比#

前提与定义#

拓扑排序的前提：图必须是有向无环图（DAG）。若图中存在环，则不存在拓扑序列。

• AOV 网（Activity On Vertex）：用顶点表示活动、有向边表示活动间先后关系的有向图
• 拓扑序列不唯一：一个 DAG 通常有多个合法的拓扑序列

Kahn 算法（BFS 入度法）#

1. 计算所有顶点的入度，将所有入度为 0 的顶点入队
2. 队列非空时，取出队首顶点并输出
3. 将该顶点的所有邻接顶点入度减 1，若入度变为 0 则入队
4. 重复直到队列为空

环检测：若最终输出的顶点数 < n，则图中存在环（环中顶点入度永远不会减为 0）。

DFS 逆后序法#

对每个未访问顶点执行 DFS，在顶点的所有后继都访问完毕回退时将该顶点压入栈，最终栈顶到栈底即为拓扑序列。

DFS 环检测（三色标记法）：若 DFS 过程中遇到状态为”访问中”的顶点，说明存在环。

复杂度分析#

核心概念#

AOE 网（Activity On Edge）：用有向无环图表示工程，顶点表示事件（Event），有向边表示活动（Activity），边的权值表示活动持续时间。

• 源点：入度为 0 的顶点（工程开始）
• 汇点：出度为 0 的顶点（工程结束）
• 关键路径：从源点到汇点的最长路径，决定工程最短工期
• 关键活动：最早开始时间等于最晚开始时间的活动（时间余量为 0）

四个时间参数#

关键活动：满足 e(i) == l(i) 的活动。

求解步骤#

1. 对 AOE 网进行拓扑排序，同时按拓扑序计算 ve[]
2. 按逆拓扑序计算 vl[]（初始化 vl[汇点] = ve[汇点]）
3. 遍历每条活动计算 e[] 和 l[]
4. 找出所有 e(i) == l(i) 的活动，即为关键活动

关键性质#

• 关键路径可能不唯一，所有关键活动构成的路径都是关键路径
• 缩短工期只能通过缩短关键活动的持续时间来实现
• 缩短某关键活动后，该路径可能不再是关键路径（其他路径变为最长），需要重新计算
• 只有缩短所有关键路径上公共的关键活动，才能确保工期缩短

易错：关键路径是最长路径，不是最短路径——这和最短路径问题的思路恰好相反。

AOV 网 vs AOE 网#