问题标签 [bellman-ford]

我读了贝尔曼福特算法。我无法理解的是为什么会有一个运行 |V|-1 次的循环（下一段中的上部循环）。

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

那么，当 i=1 时，我在松弛方法后计算的距离，是与源的最短距离吗？

请解释一下这...

我们有一个有向图（没有权重），G(V, E)，有两个顶点s，t使得 in-degree ofs和 out-degree oft等于0。我们想找到从s到的最大不同边路径数t。通过使用哪种算法，我们可以做到这一点。Bellman-Ford、Dijkestra、Huffman 和 Network Flow。我认为霍夫曼如此无关紧要，但其他人呢？我认为网络流是答案，但我不知道为什么？stackeeeers，请帮助我！

我们知道 bellman-ford 算法检查每一步中的所有边，并且对于每条边，如果，

d(v)>d(u)+w(u,v)

然后 d(v) 被更新，使得 w(u,v) 是边 (u, v) 的权重，d(u) 是顶点的最佳查找路径的长度u。如果在一个步骤中我们没有更新顶点，则算法终止。假设该算法，在迭代完成后，找到从s图 G 中的n顶点到顶点的所有最短路径k<n，以下哪项是正确的？

1) 所有最短路径中的边数s最多为k-1

2）所有最短路径的权重s最多为k-1

3）图没有负循环。

我确定其中一个是正确的，但我的助教说其中两个是正确的。对这些问题有任何想法或提示吗？

根据问题的具体情况，在单源最短路径问题的上下文中通常提到的两种算法是 Dijkstra 算法和 Bellman-Ford 算法。Dijkstra 算法适用于正边权重，而 Bellman-Ford 算法是一种泛化，也允许负边权重。

正如 Sedgewick 的“算法”一书（第 4 版）中所实现的，Dijkstra 的算法基于优先级队列，而 Bellman-Ford 算法基于普通的 FIFO 队列。但是，在我看来，这两种队列类型中的任何一种选择都不是实现算法所必需的。人们也可以用 FIFO 队列实现 Dijkstra 算法，用优先级队列实现 Bellman-Ford 算法。

为什么 Dijkstra 的算法通常使用优先级队列来实现，而贝尔曼福特算法通常使用 FIFO 队列来实现？有功能原因，还是运行时优化？

我正在研究 从书中算法的源代码获取单一源最短路径的queue-based方法，此链接位于http://algs4.cs.princeton.edu/44sp/BellmanFordSP.java。Bellman-Ford algorithmRobert Sedgewick and Kevin Wayne - Algorithms, 4th edition

我有两点，一个是疑问，另一个是代码改进建议。

1. 在上述方法中，以下是用于放松顶点距离的放松方法的代码。

   /li>

在此方法中，在找到负循环之前使用以下条件。

在上面，他们将成本除以vertices图表中的数量来检查negative cycle。这可能是因为松弛是经过V-1多次的，如果松弛持续Vth一段时间，则意味着它有循环，其中 V 是顶点数。

但我认为在基于队列的方法中，他们使用除数定期检查是否发生循环。一个循环可以在上述条件为真之前或之后发生。如果在上述条件为真之后发生循环，则算法必须等到下一次条件为真才能检测到循环，如果为真，则循环不一定会发生(cost++ % G.V() == 0)。所以我认为除数可以是任何足够小的数字，以便我们可以在适当的时间间隔后检查周期。我这样想对吗？

2. 代码改进建议是，findNegativeCycle()如果发生循环，可以使用该方法返回 true。因此。这个条件——

   if (cost++ % G.V() == 0) { findNegativeCycle(); }

可以改成——

即使findNegativeCycle()方法找到了循环，在代码中 for 循环也会继续运行。因此，如果发生循环，我们可以返回，而不是处理 for 循环的其余部分。

请分享您对以上 2 点的看法。提前致谢。

所以，基本上我正在实现一种算法来计算加权图中从一个源节点到每个其他节点的距离，如果一个节点处于负循环中，它会检测并标记该节点。

我的问题是关于我的算法的总时间复杂度。假设V是节点数和E边数。

该算法首先询问 E 行输入以指定图的边并将其插入相应的邻接列表中。这样的操作是O(E)

我应用 Bellman-Ford 算法V-1时间来了解距离，然后我V-1再次应用算法时间来检测负循环中的节点。这是2 * O(VE) = O(VE).

我打印一个距离向量，其大小V显示距离和/或节点是否处于负循环。O(V).

所以我想我的总复杂性是O(VE + V + E). 现在我的问题是：由于 VE 几乎总是大于 V+E（对于大数，它总是！），我可以将 V+E 放在复杂性中并使其简单O(VE)吗？

首先，我在 Ford Bellman claas 的构造函数中初始化值

接下来我在 FordBellman 的初始化方法的参数中有参考

在主课上我这样做

如果我调用 fb.initialize(am) 控制台什么都不显示（应该显示 cout）你能告诉我我做错了什么吗？

回购https://github.com/likoms/Graph/

在我参加的编程课上，我们学习了 Bellman-Ford SSSP 和 Djikstra 的 SSSP，我们了解到 Bellman-Ford 是基于 Kruskal 的最小生成树算法，而 Djikstra 是基于 Prim 的最小生成树算法。

我们被告知要记住 Djikstra 和 Prim 都在本地级别上运行，因为您根据已经选择的边和节点进行比较，这对我来说很有意义。我们还被告知要记住 Bellman-Ford 和 Kruskal 在全局级别上运行，因为您选择最小的边权重，而不管之前选择的节点如何。

对于 Kruskal 的算法，我可以理解为什么我们可以认为这是全局的，因为您实际上只是选择最轻或最小的边缘权重。但是对于 Bellman-Ford 的算法，我只是不明白它是如何被认为是全局的，因为您仍然需要担心之前选择的节点和边。Bellman-Ford 到底是如何基于 Kruskal 算法的，它是如何被认为是“全球”运作的？

假设我有一个具有正权或负权重的有向加权图（没有零或负权重循环）。该图是 Bellman-Ford 分析的，这意味着每个顶点都保存从源顶点到它的最轻路径的数据，以及它在最轻路径中的前身。存储从源到每个顶点的不同最短路径数量的最有效方法是什么？如果可能，我愿意在线性时间内完成 - O(V+E)。

这是我的代码：

这是我的测试数据：

结果在我的电脑上：

但是，这个加权有向图确实有一个负圆。

我误解了负循环的概念。我上面说的都是废话。这个测试加权有向图不包含负圆。

我画了一张图：

圆是 1->2->3->1

但是程序没有报告它。

分析最后的数据：

//下面的代码是测试是否有负圆。符号我已经迭代到 5

-3 > 2 + (-3) 是假的！

那么问题来了

如果我将 3->1 的权重设置为 -100，算法可以检测到负圆。

那么贝尔曼福特就是这种性质吗？