我阅读了 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时,我用松弛法计算出来的距离,就是离源最短的距离吗?
请解释一下...
Bellman--Ford 有两个适用于所有顶点的相关不变量
u
.
u
的路径,长度为dist[u]
(除非dist[u]
是INT_MAX
)。i
次迭代后,对于从源到u
的所有路径,边数不超过i
,该路径的长度不小于dist[u]
.在
V-1
次迭代之后,第二个不变量意味着从源到 u
的简单路径都不短于 dist[u]
。因此,第一个意味着我们找到的路径是最短的。
贝尔曼福特 vs 迪杰斯特拉
第4步的思路是,如果图不包含负权环,第3步保证距离最短。如果我们再次遍历所有边并为任何顶点获得更短的路径,则存在负权重循环。