Bellman-Ford算法

发表于 更新于 分类于 Waline：

贝尔曼-福特算法(Bellman–Ford algorithm )用于计算出起点到各个节点的最短距离，是一种单源最短路径算法，支持存在负权重的情况

算法原理

  • 它的原理是对图进行最多V-1次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(VE)。但算法可以进行若干种优化，提高了效率。

  • Bellman Ford算法每次对所有的边进行松弛，每次松弛都会得到一条最短路径，所以总共需要要做的松弛操作是V - 1次。在完成这么多次松弛后如果还是可以松弛的话，那么就意味着，其中包含负环。

  • 相比狄克斯特拉算法(Dijkstra algorithm),其最大优点便是Bellman–Ford支持存在负权重的情况，并且代码实现相对简单。缺点便是时间复杂度较高，达到O(V*E)，V代表顶点数，E代表边数。

可用于解决以下问题：

  • 从A出发是否存在到达各个节点的路径(有计算出值当然就可以到达)；
  • 从A出发到达各个节点最短路径(时间最少、或者路径最少等)
  • 图中是否存在负环路（权重之和为负数）

其思路为：

  1. 初始化时将起点s到各个顶点v的距离dist(s->v)赋值为∞，dist(s->s)赋值为0

  2. 后续进行最多n-1次遍历操作,对所有的边进行松弛操作,假设:

所谓的松弛，以边ab为例，若dist(a)代表起点s到达a点所需要花费的总数，dist(b)代表起点s到达b点所需要花费的总数,weight(ab)代表边ab的权重，若存在:(dist(a) +weight(ab)) < dist(b)则说明存在到b的更短的路径,s->…->a->b,更新b点的总花费为(dist(a) +weight(ab))，父节点为a

  1. 遍历都结束后，若再进行一次遍历，还能得到s到某些节点更短的路径的话，则说明存在负环路

思路上与狄克斯特拉算法(Dijkstra algorithm)最大的不同是每次都是从源点s重新出发进行"松弛"更新操作，而Dijkstra则是从源点出发向外扩逐个处理相邻的节点，不会去重复处理节点，这边也可以看出Dijkstra效率相对更高点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Graph {
  constructor(vertices, edges) {
    this.vertices = vertices;
    this.edges = edges;
  }

  initialize(source) {
    const distances = {};

    for (let i = 0; i < this.vertices.length; i++) {
      distances[this.vertices[i]] = Infinity;
    }

    distances[source] = 0;

    return distances;
  }

  relax(u, v, weight, distances) {
    if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
      distances[v] = distances[u] + weight;
    }
  }

  bellmanFord(source) {
    const distances = this.initialize(source);

    for (let i = 0; i < this.vertices.length - 1; i++) {
      for (let j = 0; j < this.edges.length; j++) {
        const { u, v, weight } = this.edges[j];
        this.relax(u, v, weight, distances);
      }
    }

    for (let i = 0; i < this.edges.length; i++) {
      const { u, v, weight } = this.edges[i];
      if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
        console.log("Negative weight cycle detected");
        return;
      }
    }

    console.log(distances);
  }
}

// 示例使用
const vertices = ["A", "B", "C", "D", "E"];
const edges = [
  { u: "A", v: "B", weight: 4 },
  { u: "A", v: "C", weight: 2 },
  { u: "B", v: "C", weight: -3 },
  { u: "B", v: "D", weight: 2 },
  { u: "D", v: "E", weight: 3 },
  { u: "E", v: "D", weight: -2 },
];

const graph = new Graph(vertices, edges);
graph.bellmanFord("A");