Bellman-Ford 算法

贝尔曼-福特（Bellman–Ford）算法是一种基于松弛（relax）操作的最短路径算法，可以求出有负权的图的最短路径，并可以对最短路径不存在的情况进行判断。

记号

为了方便叙述，这里先给出下文将会用到的一些记号的含义。

\(n\) 为图上点的数目，\(m\) 为图上边的数目；
\(s\) 为最短路径的源点；
\(D(u)\) 为 \(s\) 点到 \(u\) 点的实际最短路径长度；
\(distance(u)\) 为 \(s\) 点到 \(u\) 点的估计最短路径长度；

任何时候都有：\(distance(u) \geq D(u)\)，特别地，当最短路算法终止时，应有 \(distance(u)=D(u)\)。
\(w(u,v)\) 为 \((u,v)\) 这一条边的权重。

过程

先介绍 Bellman–Ford 算法要用到的松弛操作（Dijkstra 算法也会用到松弛操作）。

对于边 \(E(u,v)\)，松弛操作对应下面的式子：

\[distance(v) = \min(distance(v),distance(u) + w(u, v)) \]

这么做的含义是显然的：我们尝试用 \(S \to u \to v\)（其中 \(S \to u\) 的路径取最短路径）这条路径去更新 \(v\) 点最短路径的长度，如果这条路径更优，就进行更新。

Bellman–Ford 算法所做的，就是不断尝试对图上每一条边进行松弛，我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

每次循环是 \(O(m)\) 的，那么最多会循环多少次呢？

在最短路存在的情况下，由于一次松弛操作会使最短路径的边数至少 \(+1\)，而最短路径的边数最多为 \(n-1\)，因此整个算法最多执行 \(n-1\) 轮松弛操作，因此，总时间复杂度为 \(O(nm)\)。

但还有一种情况，如果从 \(S\) 点出发，抵达一个负环时，松弛操作会无休止地进行下去。

注意到前面的论证中已经说明了，对于最短路存在的图，松弛操作最多只会执行 \(n-1\) 轮，因此如果第 \(n\) 轮循环时仍然存在能松弛的边，说明从 \(S\) 点出发，能够抵达一个负环。

举例

应用

应用1：Leetcode 787. K 站中转内最便宜的航班

题目

787. K 站中转内最便宜的航班

有 \(n\) 个城市通过一些航班连接。给你一个数组 \(flights\) ，其中 \(flights[i] = [from_i, to_i, price_i]\) ，表示该航班都从城市 \(from_i\) 开始，以价格 \(price_i\) 抵达 \(to_i\)。
现在给定所有的城市和航班，以及出发城市 \(src\) 和目的地 \(dst\)，你的任务是找到出一条最多经过 \(k\) 站中转的路线，使得从 \(src\) 到 \(dst\) 的价格最便宜，并返回该价格。如果不存在这样的路线，则输出 \(-1\)。

示例 1：

输入:
\(n = 3\), \(edges = [[0,1,100],[1,2,100],[0,2,500]]\)
\(src = 0\), \(dst = 2\), \(k = 1\)
输出: 200
解释:
城市航班图如下

从城市 \(0\) 到城市 \(2\) 在 \(1\) 站中转以内的最便宜价格是 200，如图中红色所示。

分析

方法一：动态规划

假设 \(dp[t][i]\) 表示从城市 \(src\) 出发，恰好搭乘 \(t\) 次航班，到达城市 \(i\) 的最小花费。

边界条件

当 \(t = 0\)，即出发城市就是 \(src\) 时，显然有：

如果 \(i = src\) ，即出发城市是 \(src\) 时，所需的花费为零；
如果 \(i \ne src\)，即出发的城市不是 \(src\) 时，所需的花费为 \(INF\)。

因此，边界条件：

\[dp[0][i] = \begin{cases} 0 \ , i = src\\ +\infty \ , i \ne src \end{cases} \]

状态转移

这里，我们用 \(w_{(u, v)}\) 表示 从城市 \(u\) 到城市 \(v\) 的花费，那么，我们可以枚举最后一次航班的起点 \(u\)，从而找到花费最少的线路。

因此，搭乘 \(t\) 次航班到达城市 \(v\) 的花费，可以通过 前 \(t-1\)次航班的最小花费 \(d[t - 1][u]\) 加上 最后一次航班的花费 \(w_{(u, v)}\)，即：

\[dp[t][v] = \min_{(u,v)} \{dp[t - 1][u] + w_{(u, v)}\}, (u,v) \in flights \]

由于我们最多只能中转 \(k\) 次，即最少搭乘 \(1\) 次航班，最多搭乘 \(k + 1\) 次航班，因此，最终的答案 \(result\) 就是

\[result = \min_{t = 1}^{k + 1} \{dp[t][dst]\} \]

方法二：Bellman Ford 算法

题目可以等价转换为：在有向加权图上，经过最多不超过 \(k + 1\) 条边的最短路径，因此，可以使用 Bellman Ford 算法求解。

注意：在遍历所有的“点对/边”进行松弛操作前，需要先对 \(distance\) 进行备份，否则会出现 本次松弛操作所使用到的边，也是在同一次迭代所更新的，从而不满足边数限制的要求。

代码实现

方法一：

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        f = [[float("inf")] * n for _ in range(k + 2)]
        f[0][src] = 0

        # 最多可以中转k次，即最多可搭乘航班k+1次
        for time in range(1, k + 2):
            for start, end, cost in flights:
                f[time][end] = min(f[time][end], f[time - 1][start] + cost)

        result = min(f[t][dst] for t in range(1, k + 2))
        return -1 if result == float("inf") else result

复杂度分析：

时间复杂度：\(O(k \times (n + n))\)，其中，m 为边的条数。
空间复杂度：\(O(n \times k)\)

方法二：

class Edge(object):
    def __init__(self, start, end, weight):
        self.start = start
        self.end = end
        self.weight = weight

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        edges = list()
        for _start, _end, _cost in flights:
            edges.append(Edge(_start, _end, _cost))
        distances = self.bellman_ford(src, n, edges, k)
        return distances[dst] if distances[dst] != float("inf") else -1

    def bellman_ford(self, src, n, edges, k):
        distance = [float("inf")] * n
        distance[src] = 0
        for i in range(k + 1):
            _distance = distance[:]
            for edge in edges:
                u = edge.start
                v = edge.end
                w = edge.weight
                distance[v] = min(distance[v], _distance[u] + w)
        return distance

复杂度分析：