1

我读了贝尔曼福特算法。我无法理解的是为什么会有一个运行 |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 时，我在松弛方法后计算的距离，是与源的最短距离吗？

请解释一下这...

4

1 回答 1

3

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

  1. 存在从源到u长度的路径dist[u]（除非dist[u]是INT_MAX）。
  2. i 在外循环的迭代之后，对于从源到u有i或更少边的所有路径，该路径的长度不小于dist[u].

在V-1迭代之后，第二个不变量意味着从源到u的简单路径不短于dist[u]。因此，第一个意味着我们找到的路径是最短的。

于 2015-03-04T15:17:57.817 回答