贝尔曼福特算法讲解

Question

我阅读了 Bellman Ford 算法。我无法理解的是为什么有一个循环运行了 |V|-1 次（下一段中的上循环）。

for ( i = 1; i <= V-1; i++)
{
    for (j = 0; j < E; j++)
    {
        int u = graph->edge[j].src;
        int v = graph->edge[j].dest;
        int weight = graph->edge[j].weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
        {
            dist[v] = dist[u] + weight;

        }
    }

我经历了几个教程。所有人都在说同一件事，即可以有最大值 |V| – 任何简单路径中的 1 个边，这就是外循环运行 |v| 的原因– 1 次。这个想法是，假设没有负权重循环，如果我们计算了最多 i 条边的最短路径，那么对所有边的迭代保证给出最多 (i+1) 条边的最短路径。

那么，当i=1时，我用松弛法计算出来的距离，就是离源最短的距离吗？

请解释一下...

Answer 1

Bellman--Ford 有两个适用于所有顶点的相关不变量

u

.

1. 存在一条从源到

   u

   的路径，长度为

   dist[u]

   （除非

   dist[u]

   是

   INT_MAX

   ）。
2. 外循环

   i

   次迭代后，对于从源到

   u

   的所有路径，边数不超过

   i

   ，该路径的长度不小于

   dist[u]

   .

在

V-1

次迭代之后，第二个不变量意味着从源到

u

的简单路径都不短于

dist[u]

。因此，第一个意味着我们找到的路径是最短的。

Answer 2

贝尔曼福特 vs 迪杰斯特拉

1. Bellman 也适用于负加权图，而 Dijkstra 仅适用于正加权图。
2. Bellman 的 TC O(V*E) 大于 Dijkstra 的 TC，即 O(V+E)。

• Bellman ford的步骤：-

1. 首先我们初始化一个默认值非常大的距离数组。
2. source的数组值设置为0.
3. 首先尝试在第一次迭代中找到最短路径。
4. 现在，再次遍历所有节点，如果我们再次找到新的最短路径然后出现负循环，则尝试执行与第 3 步相同的操作。

第4步的思路是，如果图不包含负权环，第3步保证距离最短。如果我们再次遍历所有边并为任何顶点获得更短的路径，则存在负权重循环。