Bellman Ford 算法

Bellman Ford 算法是一种单源最短路径算法。该算法用于查找从单个顶点到加权图中所有其他顶点的最短距离。有许多其他算法用于查找最短路径，例如 Dijkstra 算法等。如果加权图包含负权重值，则 Dijkstra 算法不能保证其产生正确答案。与 Dijkstra 算法相比，bellman ford 算法即使在加权图包含负权重值的情况下也能保证正确答案。

该算法的规则

考虑下面的图

正如我们在上面的图中观察到的，一些权重是负数。上面的图包含 6 个顶点，所以我们将迭代放松直到 5 个顶点。这里，我们将放松所有边 5 次。循环将迭代 5 次以获得正确答案。如果循环迭代次数超过 5 次，答案也将保持不变，即顶点之间的距离不会发生变化。

放松意味着

为了找到上面图的最短路径，第一步是记下所有给出的边

(A, B), (A, C), (A, D), (B, E), (C, E), (D, C), (D, F), (E, F), (C, B)

让我们将源顶点视为 'A'；因此，顶点 A 的距离值为 0，所有其他顶点的距离值都为无穷大，如下所示

由于图有六个顶点，因此将有五次迭代。

第一次迭代

考虑边 (A, B)。将顶点 'A' 表示为 'u'，顶点 'B' 表示为 'v'。现在使用放松公式

d(u) = 0

d(v) = ∞

c(u , v) = 6

由于 (0 + 6) 小于 ∞，因此更新

d(v) = 0 + 6 = 6

因此，顶点 B 的距离是 6。

考虑边 (A, C)。将顶点 'A' 表示为 'u'，顶点 'C' 表示为 'v'。现在使用放松公式

d(u) = 0

d(v) = ∞

c(u , v) = 4

由于 (0 + 4) 小于 ∞，因此更新

d(v) = 0 + 4 = 4

因此，顶点 C 的距离是 4。

考虑边 (A, D)。将顶点 'A' 表示为 'u'，顶点 'D' 表示为 'v'。现在使用放松公式

d(u) = 0

d(v) = ∞

c(u , v) = 5

由于 (0 + 5) 小于 ∞，因此更新

d(v) = 0 + 5 = 5

因此，顶点 D 的距离是 5。

考虑边 (B, E)。将顶点 'B' 表示为 'u'，顶点 'E' 表示为 'v'。现在使用放松公式

d(u) = 6

d(v) = ∞

c(u , v) = -1

由于 (6 - 1) 小于 ∞，因此更新

d(v) = 6 - 1= 5

因此，顶点 E 的距离是 5。

考虑边 (C, E)。将顶点 'C' 表示为 'u'，顶点 'E' 表示为 'v'。现在使用放松公式

d(u) = 4

d(v) = 5

c(u , v) = 3

由于 (4 + 3) 大于 5，因此不会更新。顶点 E 的值为 5。

考虑边 (D, C)。将顶点 'D' 表示为 'u'，顶点 'C' 表示为 'v'。现在使用放松公式

d(u) = 5

d(v) = 4

c(u , v) = -2

由于 (5 -2) 小于 4，因此更新

d(v) = 5 - 2 = 3

因此，顶点 C 的距离是 3。

考虑边 (D, F)。将顶点 'D' 表示为 'u'，顶点 'F' 表示为 'v'。现在使用放松公式

d(u) = 5

d(v) = ∞

c(u , v) = -1

由于 (5 -1) 小于 ∞，因此更新

d(v) = 5 - 1 = 4

因此，顶点 F 的距离是 4。

考虑边 (E, F)。将顶点 'E' 表示为 'u'，顶点 'F' 表示为 'v'。现在使用放松公式

d(u) = 5

d(v) = ∞

c(u , v) = 3

由于 (5 + 3) 大于 4，因此顶点 F 的距离值不会更新。

考虑边 (C, B)。将顶点 'C' 表示为 'u'，顶点 'B' 表示为 'v'。现在使用放松公式

d(u) = 3

d(v) = 6

c(u , v) = -2

由于 (3 - 2) 小于 6，因此更新

d(v) = 3 - 2 = 1

因此，顶点 B 的距离是 1。

现在第一个迭代已完成。我们进行第二次迭代。

第二次迭代

在第二次迭代中，我们再次检查所有边。第一条边是 (A, B)。由于 (0 + 6) 大于 1，因此顶点 B 不会更新。

下一条边是 (A, C)。由于 (0 + 4) 大于 3，因此顶点 C 不会更新。

下一条边是 (A, D)。由于 (0 + 5) 等于 5，因此顶点 D 不会更新。

下一条边是 (B, E)。由于 (1 - 1) 等于 0，小于 5，因此更新

d(v) = d(u) + c(u, v)

d(E) = d(B) +c(B , E)

= 1 - 1 = 0

下一条边是 (C, E)。由于 (3 + 3) 等于 6，大于 5，因此顶点 E 不会更新。

下一条边是 (D, C)。由于 (5 - 2) 等于 3，因此顶点 C 不会更新。

下一条边是 (D, F)。由于 (5 - 1) 等于 4，因此顶点 F 不会更新。

下一条边是 (E, F)。由于 (5 + 3) 等于 8，大于 4，因此顶点 F 的距离值不会更新。

下一条边是 (C, B)。由于 (3 - 2) 等于 1，因此顶点 B 不会更新。

第三次迭代

我们将执行与之前迭代相同的步骤。我们将观察到顶点距离不会发生更新。

时间复杂度

Bellman ford 算法的时间复杂度为 O(E|V| - 1)。

Bellman ford 算法的缺点

• 如果一个环的边之和为负数，bellman ford 算法将无法产生正确答案。让我们通过一个例子来理解这个属性。考虑下面的图。
  
• 在上面的图中，我们将顶点 1 视为源顶点并为其提供 0 值。我们为其他顶点提供无穷大值，如下所示
  
  边可以写成
  (1, 3), (1, 2), (2, 4), (3, 2), (4, 3)

第一次迭代

考虑边 (1, 3)。将顶点 '1' 表示为 'u'，顶点 '3' 表示为 'v'。现在使用放松公式

d(u) = 0

d(v) = ∞

c(u , v) = 5

由于 (0 + 5) 小于 ∞，因此更新

d(v) = 0 + 5 = 5

因此，顶点 3 的距离是 5。

考虑边 (1, 2)。将顶点 '1' 表示为 'u'，顶点 '2' 表示为 'v'。现在使用放松公式

d(u) = 0

d(v) = ∞

c(u , v) = 4

由于 (0 + 4) 小于 ∞，因此更新

d(v) = 0 + 4 = 4

因此，顶点 2 的距离是 4。

考虑边 (3, 2)。将顶点 '3' 表示为 'u'，顶点 '2' 表示为 'v'。现在使用放松公式

d(u) = 5

d(v) = 4

c(u , v) = 7

由于 (5 + 7) 大于 4，因此顶点 2 不会更新。

考虑边 (2, 4)。将顶点 '2' 表示为 'u'，顶点 '4' 表示为 'v'。现在使用放松公式

d(u) = 4

d(v) = ∞

c(u , v) = 7

由于 (4 + 7) 等于 11，小于 ∞，因此更新

d(v) = 4 + 7 = 11

因此，顶点 4 的距离是 11。

考虑边 (4, 3)。将顶点 '4' 表示为 'u'，顶点 '3' 表示为 'v'。现在使用放松公式

d(u) = 11

d(v) = 5

c(u , v) = -15

由于 (11 - 15) 等于 -4，小于 5，因此更新

d(v) = 11 - 15 = -4

因此，顶点 3 的距离是 -4。

现在我们进行第二次迭代。

第二次迭代

现在，我们再次检查所有边。第一条边是 (1, 3)。由于 (0 + 5) 等于 5，大于 -4，因此顶点 3 不会更新。

下一条边是 (1, 2)。由于 (0 + 4) 等于 4，因此顶点 2 不会更新。

下一条边是 (3, 2)。由于 (-4 + 7) 等于 3，小于 4，因此更新

d(v) = d(u) + c(u, v)

d(2) = d(3) +c(3, 2)

= -4 + 7 = 3

因此，顶点 2 的值为 3。

下一条边是 (2, 4)。由于 ( 3+7) 等于 10，小于 11，因此更新

d(v) = d(u) + c(u, v)

d(4) = d(2) +c(2, 4)

= 3 + 7 = 10

因此，顶点 4 的值为 10。

下一条边是 (4, 3)。由于 (10 - 15) 等于 -5，小于 -4，因此更新

d(v) = d(u) + c(u, v)

d(3) = d(4) +c(4, 3)

= 10 - 15 = -5

因此，顶点 3 的值为 -5。

现在我们进行第三次迭代。

第三次迭代

现在，我们再次检查所有边。第一条边是 (1, 3)。由于 (0 + 5) 等于 5，大于 -5，因此顶点 3 不会更新。

下一条边是 (1, 2)。由于 (0 + 4) 大于 3，因此顶点 2 不会更新。

下一条边是 (3, 2)。由于 (-5 + 7) 等于 2，小于 3，因此更新

d(v) = d(u) + c(u, v)

d(2) = d(3) +c(3, 2)

= -5 + 7 = 2

因此，顶点 2 的值为 2。

下一条边是 (2, 4)。由于 (2 + 7) 等于 9，小于 10，因此更新

d(v) = d(u) + c(u, v)

d(4) = d(2) +c(2, 4)

= 2 + 7 = 9

因此，顶点 4 的值为 9。

下一条边是 (4, 3)。由于 (9 - 15) 等于 -6，小于 -5，因此更新

d(v) = d(u) + c(u, v)

d(3) = d(4) +c(4, 3)

= 9 - 15 = -6

因此，顶点 3 的值为 -6。

由于图包含 4 个顶点，根据 bellman ford 算法，只有 3 次迭代。如果我们尝试对图进行第 4 次迭代，顶点到给定顶点的距离应该不会改变。如果距离发生变化，则意味着 bellman ford 算法没有提供正确的答案。

第 4 次迭代

第一条边是 (1, 3)。由于 (0 +5) 等于 5，大于 -6，因此顶点 3 不会发生变化。

下一条边是 (1, 2)。由于 (0 + 4) 大于 2，因此不会更新。

下一条边是 (3, 2)。由于 (-6 + 7) 等于 1，小于 3，因此更新

d(v) = d(u) + c(u, v)

d(2) = d(3) +c(3, 2)

= -6 + 7 = 1

在这种情况下，顶点的值被更新了。因此，我们得出结论，当图包含负权重环时，bellman ford 算法不起作用。

因此，顶点 2 的值为 1。