贝尔曼福特算法讲解

问题描述 投票:0回答:2

我阅读了 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时,我用松弛法计算出来的距离,就是离源最短的距离吗?

请解释一下...

algorithm graph-algorithm bellman-ford
2个回答
3
投票

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

u
.

  1. 存在一条从源到
    u
    的路径,长度为
    dist[u]
    (除非
    dist[u]
    INT_MAX
    )。
  2. 外循环
    i
    次迭代后,对于从源到
    u
    的所有路径,边数不超过
    i
    ,该路径的长度不小于
    dist[u]
    .

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


0
投票

贝尔曼福特 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步保证距离最短。如果我们再次遍历所有边并为任何顶点获得更短的路径,则存在负权重循环。

© www.soinside.com 2019 - 2024. All rights reserved.