问题背景阐述以及分类

在一个有权有向图(weighted directed graph)中，我们想知道从一个节点到其他某一个节点的路径的权和，注意权重可能是负数，我们这里假设图本身没有形成环
那么问题会被分成两类

  1. Single-Source Shortest Paths (SSSP): 单个源出发到达某一节点的最短路径
  2. All-pairs Shortest Paths (ASAP): 任意一对节点之间的最短路径

两则引理

引理1

如果从 ss 到 tt 的最短路径经过 vv 节点，那么 ss 到 vv 和 vv 到 tt 均为最短路径

引理2

如果图中没有负权回路，那么从 ss 到 tt 的最短路径中不会存在回路

递归法解决 SSSP 问题

我们可以得到递归公式:

dist(s,t)=min⁡v∈neighbors(s){dist(s,v)+w(v,t)}dist(s, t) = \min_{v \in \text{neighbors}(s)} \{dist(s, v) + w(v, t)\}

但是这个递归公式可能会存在一个死循环：如果 t,vt,v 两个节点双向相通，由于递归没有到达base情况，因此计算 dist(s,t)dist (s,t) 的时候会计算 dist(s,v)dist(s,v), 计算 dist(s,v)dist(s,v) 的时候会计算 dist(s,t)dist(s,t)，那么我们就会一直递归下去，所以我们需要额外加一个势能变量来让其逐步下落

Bellman-Ford 算法

我们将递归函数变成 dist(i)(s,t)dist^{(i)}(s, t)，其中 ii 代表步长，这样在不断前进的过程中，由于每次递归会走到当前节点的上一步，所以每次数值 i 必定会减少 1，这样我们就可以保证不会陷入死循环
这样我们新的递归公式表述为

dist(i)(s,t)=min⁡v∈neighbors(s){dist(i−1)(s,v)+w(v,t)}dist^{(i)}(s, t) = \min_{v \in \text{neighbors}(s)} \{dist^{(i-1)}(s, v) + w(v, t)\}

Base Case

当 i = 0 时，表示步长为 0，不前进就到达，如果 s≠vs\neq v 那么不存在这种情况，我们令其为 ∞\infty，否则为 0

动态规划解决

我们将

1
2
3
4
5
6
7
8
9
def SSSP(G, s):
  table := 2D-array index from 0 to n-1 in both dimensions
  table(0,0) = 0  # base case for s
  for v = 1 to n-1:
    table(0, v) = ∞
  for i = 1 to n-1:
    for v = 0 to n-1:
      table(i, v) = min{table(i-1, u) + w(u, v) for u in neighbors(v)}
  return min{table(n-1, v) for v in 0 to n-1}

复杂度分析

由于会遍历一个图的每个节点以及其相邻节点（这个就是 edge 的数量）因此时间复杂度是 O(∣V∣⋅∣E∣)O(|V| \cdot |E|)

负数环的检测

我们可以在 Bellman-Ford 算法中加入一个检测负数环的步骤，即我们将势方程 的上限从 i=ni = n 变成 i=2ni = 2n 再次进行检测，如果出现 min⁡(2n)dist(s,t)<min⁡dist(n)(s,t)\min_{(2n)}dist(s, t) < \min dist_{(n)}(s, t)，那么说明存在负数环

递归法解决 ASAP 问题

简单的用 BF 算法来思考其实就是对每个点进行计算找到最短路径，但是这样的复杂度是 O(∣V∣2⋅∣E∣)O(|V|^2 \cdot |E|)，我们可以用 Floyd-Warshall 算法来解决这个问题

Floyd-Warshall 算法

这个算法就是将 BF 算法中的 potential 量转变成 ii 表示从 ss 到 tt 的经过中间节点的数量，且我们令中间节点的命名为 v1⋯viv_1\cdots v_i, 那么当我们从 ii 到 i−1i - 1 的时候，就可以认为是 没有选择或者选择了 viv_i 作为中间节点
这样我们就可以得到递归公式

dist(i)(s,t)=min⁡{dist(i−1)(s,t),dist(i−1)(s,vi)+dist(i−1)(vi,t)}dist^{(i)}(s, t) = \min\{dist^{(i-1)}(s, t), dist^{(i-1)}(s, v_i) + dist^{(i-1)}(v_i, t)\}

前者表示没有选择第 ii 个节点，后者表示选择了第 ii 个节点

动态规划解决

1
2
3
4
5
6
7
8
9
10
def ASAP(G):
  table := 3D-array index from 0 to n-1 in all dimensions
  for v = 0 to n-1:
    for u = 0 to n-1:
      table(0, u, v) = w(u, v)  # base case, 不经过中间节点直接到达
  for i = 1 to n-1:
    for u = 0 to n-1:
      for v = 0 to n-1:
        table(i, u, v) = min{table(i-1, u, v), table(i-1, u, i) + table(i-1, i, v)}
  return min{table(n-1, u, v) for u in 0 to n-1, v in 0 to n-1}

复杂度分析

由于每次都会遍历所有的节点，因此时间复杂度是 O(∣V∣3)O(|V|^3)
这个算法和 BF 直接运用到 三维的 O(∣V∣2∣E∣)O(|V|^2 |E|) 复杂度而言，在稠密图(edge很多)上表现更好