介绍

贝尔曼 - 福特算法（英语：Bellman–Ford algorithm），求解单源最短路径问题的一种算法。它的原理是对图进行${\displaystyle |V|-1}$ 次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达$O(|V||E|)$。但算法可以进行若干种优化，提高了效率。

Bellman-Ford 算法是一种用于计算带权有向图中单源最短路径（SSSP：Single-Source Shortest Path）的算法。该算法由 Richard Bellman 和 Lester Ford 分别发表于 1958 年和 1956 年，而实际上 Edward F. Moore 也在 1957 年发布了相同的算法，因此，此算法也常被称为 Bellman-Ford-Moore 算法。

Bellman-Ford 算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。

Bellman-Ford 算法采用动态规划（Dynamic Programming）进行设计，实现的时间复杂度为 O (V*E)，其中 V 为顶点数量，E 为边的数量。Dijkstra 算法采用贪心算法（Greedy Algorithm）范式进行设计，普通实现的时间复杂度为 O (V2)，若基于 Fibonacci heap 的最小优先队列实现版本则时间复杂度为 O (E + VlogV)。

Bellman-Ford 算法描述：

• 创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，初始均为 Infinite，源顶点距离为 0；
• 计算最短路径，执行 V - 1 次遍历；
• 对于图中的每条边：如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d，则更新终点 v 的距离值 d；
• 检测图中是否有负权边形成了环，遍历图中的所有边，计算 u 至 v 的距离，如果对于 v 存在更小的距离，则说明存在环；

原理

• 松弛：每次松弛操作实际上是对相邻节点的访问，第 n 次松弛操作保证了所有深度为 n 的路径最短。由于图的最短路径最长不会经过超过${\displaystyle |V|-1}$ 条边，所以可知贝尔曼 - 福特算法所得为最短路径。
• 负边权操作：与迪科斯彻算法不同的是，迪科斯彻算法的基本操作 “拓展” 是在深度上寻路，而 “松弛” 操作则是在广度上寻路，这就确定了贝尔曼 - 福特算法可以对负边进行操作而不会影响结果。
• 负权环判定：因为负权环可以无限制的降低总花费，所以如果发现第 n 次操作仍可降低花销，就一定存在负权环。

优化

• 循环的提前跳出：在实际操作中，贝尔曼 - 福特算法经常会在未达到 V - 1 次前就出解，其实 V - 1 是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。
• 队列优化：西南交通大学的段凡丁于 1994 年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。原文中提出该算法的复杂度为 O (k|E|)，是个比较小的系数，但该结论未得到广泛认可。参见：最短路径快速算法_百度百科 (opens new window)

演示

参考：

• The Bellman-Ford Algorithm (opens new window)
• BELLMAN-FORD DEMO (opens new window)

实现

JavaScript

/*
The Bellman–Ford algorithm is an algorithm that computes shortest paths
from a single source vertex to all of the other vertices in a weighted digraph.
It also detects negative weight cycle.

Complexity:
    Worst-case performance O(VE)
    Best-case performance O(E)
    Worst-case space complexity O(V)

Reference:
    https://en.wikipedia.org/wiki/Bellman–Ford_algorithm
    https://cp-algorithms.com/graph/bellman_ford.html

*/

/**
 *
 * @param graph Graph in the format (u, v, w) where
 *  the edge is from vertex u to v. And weight
 *  of the edge is w.
 * @param V Number of vertices in graph
 * @param E Number of edges in graph
 * @param src Starting node
 * @param dest Destination node
 * @returns Shortest distance from source to destination
 */
function BellmanFord (graph, V, E, src, dest) {
  // Initialize distance of all vertices as infinite.
  const dis = Array(V).fill(Infinity)
  // initialize distance of source as 0
  dis[src] = 0

  // Relax all edges |V| - 1 times. A simple
  // shortest path from src to any other
  // vertex can have at-most |V| - 1 edges
  for (let i = 0; i < V - 1; i++) {
    for (let j = 0; j < E; j++) {
      if ((dis[graph[j][0]] + graph[j][2]) < dis[graph[j][1]]) { 
        dis[graph[j][1]] = dis[graph[j][0]] + graph[j][2] 
      }
    }
  }
  // check for negative-weight cycles.
  for (let i = 0; i < E; i++) {
    const x = graph[i][0]
    const y = graph[i][1]
    const weight = graph[i][2]
    if ((dis[x] !== Infinity) && (dis[x] + weight < dis[y])) {
      return null
    }
  }
  for (let i = 0; i < V; i++) {
    if (i === dest) return dis[i]
  }
}

参考

• 贝尔曼 - 福特算法 - 维基百科，自由的百科全书 (opens new window)
• Bellman-ford 算法 - 知乎 (opens new window)
• 贝尔曼 - 福特算法_百度百科 (opens new window)
• 算法系列 —— 贝尔曼福特算法（Bellman-Ford） (opens new window)