跳转至

3 基本图算法

最小生成树

  最小生成树的概念，是针对于无向连通图的。有两个贪心算法。

Prim 算法

  从一个源点 $S$ 开始。在不形成环的情况下，每次选择连接 $S$ 所在的连通分支的边中，权重最小的那个。直到只剩下一个连通分支。

Kruskal 算法

  在不形成环的情况下，从所有的边中选择权重最小的，直到只剩下一个连通分支。

单源最短路径

Bellman-Ford 算法

  如果图 $G$ 有 $n$ 个节点，在初始化之后，执行 $n-1$ 轮松弛。每轮松弛都是按照特定的顺序松弛 $G$ 中所有的边。根据操作后结点的 $d$ 值是否满足三角不等式，返回bool值，代表该图中最短路径是否能够定义。

Bellman-Ford 算法的具体运行方式

  初始化操作（后面的 Dijkstra 也是）：对所有的结点 $v\in V$，置 $v.d=\infty\ \mathrm{and}\ v.\pi=\mathrm{NIL}$。然后置 $s.d=0$，其中 $s$ 是源节点。
  Bellman-Ford 返回的bool值，也代表“图 $G$ 中是否含有可以由 $s$ 到达的负权重回路”。一旦返回true，那么对于所有的结点 $v\in V$，都有 $\delta(s,v)=v.d$。
  在手动运行Bellman-Ford算法的时候，有两种松弛方式：
  （1）用每轮松弛操作前的 $d$ 值进行松弛，是一种“并行松弛”。每轮松弛后的结果与边松弛的先后顺序无关，我们可以按照任意的顺序对这些边进行松弛。
  （2）每次松弛时采用最新的 $d$ 值，是一种“串行松弛”。这个依赖于每条边的松弛顺序，也就是说，松弛顺序不同，一轮松弛得到的结果也会有区别。
  比如我在第一次松弛的时候，得到了 $u.d=6$，$v.d=7$，图中有 $w(u,v)=3$。在进行第二轮松弛的时候，$(u,v)$ 被松弛之前，先更新了 $u.d =2$。如果是采取松弛方式（2），在后续对 $(u,v)$ 进行松弛的时候，$v.d$ 会被更新为 $2+3=5$；如果是采取松弛方式（1），在后续对 $(u,v)$ 进行松弛的时候，使用的 $u.d$ 仍然是第一轮松弛得到的 $6$，所以 $v.d$ 不会改变。
  Bellman-Ford实际的运行方式是松弛方式（2），但不理解有的题目要我们用方式（1）。不过，虽然方式（2）每轮松弛的结果依赖边松弛的顺序，但是在算法返回true的情况下，最终的结果和这个松弛顺序是无关的——最终 $v.d$ 都会收敛到 $\delta(s,v)$。

  算法的优点是可以处理含有负权重边的图，缺点是时间复杂度 $O(VE)$ 有点大。简单图的边数 $E$ 可以达到 $O(V^2)$ 的规模，这个时候 Bellman-Ford 算法的时间复杂度就是 $O(n^3)$。

Dijkstra 算法

  维持一个集合 $S$，在初始化之后，不断重复这样的操作：

  1. 对于不在 $S$ 中的结点，找到$d$值最小的那个 $v$ 加入 $S$。
  2. 松弛所有从 $v$ 发出的边。
  3. 最后，所有的结点都会进入 $S$，此时算法终止。

  Dijkstra 算法在时间复杂度上优于 Bellman-Ford 算法， 不经优化就能达到 $O(n^2)$ 的复杂度，但是不能处理含有负权重边的图。

SPFA算法

  维持一个队列 $Q$，初始时有且只有源节点 $s$。重复这样的操作：

  1. 每次从 $Q$ 中出队队首节点 $v$，松弛所有从 $v$ 发出的边。
  2. 在松弛中 $d$ 值改变的结点都入队。
  3. 直到 $Q$ 空时，算法终止。

  它的优点是可以处理含有负权重边的图，并且时间复杂度也显著优于 Bellman-Ford 算法。但是貌似泛用性不强，容易被卡。

多源最短路径

一种自然的想法

  对从 $u$ 到 $v$ 的路径长度 $l$ 进行动态规划：求出所有节点对在路径长度不大于 $l=l _ 0$ 时的最短路径，就可以自底向上地推导所有结点对在路径长度不大于 $l=l _ 0+1$ 时的最短路径。
  这种动态规划的时间复杂度是 $O(n^3\lg n)$。

Floyd-Warshall 算法

  Floyd-Warshall 算法也是一个动态规划的算法，但思路是先求出所有结点对在经过中间结点 $v _ c$ 编号 $c\in [1,k]$ 时的最短路径，再自底向上地推导出所有节点在经过中间节点编号 $c\in [1,k+1]$ 时的最短路径。
  时间复杂度可以降至 $O(n^3)$。

Floyd-Warshall 算法的状态转移方程

  Floy-Warshall 算法可以看作是三维 DP。数组 $dp[i][j][k]$ 表示在中间节点编号 $c\in [1,k]$ 的时候，从结点 $i$ 结点到 $j$ 的最短距离。状态转移方程是： $$dp[i][j][k]=\min(dp[i][j][k-1],dp[i][k][k-1]+dp[k][j][k-1])\tag{3.1}$$   由于状态转移方程中 $dp[…][…][k]$ 只和 $dp[…][…][k-1]$ 有关，其实可以把 $dp$ 数组的第三维压掉，变成二维 DP。

Johnson算法

  Johnson算法的设计还是比较巧妙的，它的核心思想就是在确保最短路径不变的情况下，把图 $G$ 的边权 $w$ 转化成非负的权重 $\hat w$，让 Dijkstra 能跑起来。

Johnson 算法的具体运行方式

  Johnson 算法引入一个外部节点 $s$ 加入 $V$ 中，同时向 $E$ 中添加 $n$ 条由 $s$ 发出、到 $V$ 中的结点的边，生成图 $G^\prime$。在图 $G^\prime$ 中以 $s$ 为源点运行 Bellman-Ford 算法，给每个节点标记一个 $h$ 值 $h(v)=\delta(s,v)$。
  如果 Bellman-Ford 算法返回true，说明图 $G$ 不含负权重回路，以 $\hat w(u,v)=w(u,v)+h(u)-h(v)$ 运行 Dijkstra 算法，能够得到各结点对之间的最短距离 $\hat\delta(u,v)$。修正后的 $\delta(u,v)=\hat\delta(u,v)-h(u)+h(v)$ 就是我们需要求的结果。

  Johnson 算法适用于稀疏图，究其原因还是 Bellman-Ford 在非稀疏图上跑起来很需要时间。