为什么Bellman-Ford不能用于单源最长路径？
Dijkstra不能用于最长路径，因为它使用的属性是当前最短路径肯定比其他路径短。这是正确的，当然，假设没有负边缘权重。这个概念也是为什么最长路径在Dijkstra上不起作用的原因，因为当前最长的路径不能保证以后不会有另一个更长的路径取更大的值。
另一方面，贝尔曼福特提供了在较差的性能负权重的灵活性。这意味着，对于贝尔曼福特来说，它不像迪克斯特拉那样在同样贪婪的财产上工作。所以这就是为什么我很困惑--为什么Bellman Ford不能用于单源最长路径问题（NP难）？例如，我们可以简单地将图的所有权重乘以-1并找到最短路径，这将是原始图的最长路径。
共有1个答案
Bellman-Ford允许弧被重用（否则即使存在负循环，也会有定义良好的最短路径），而单源最长路径问题的NP困难来自于它没有这样做的事实（否则，您可以在将所有权重乘以-1后使用Bellman-Ford）。
-
我曾尝试实现Bellman-ford单源最短路径的邻接矩阵，但它并没有检测到负循环中的一个顶点 同样的算法适用于边缘列表，但在相邻矩阵中给出了误差 我的代码： 输出： 2时有一个-ve循环-
-
我正在做一个有向图的项目，其中边的权重都依赖于变量x。我试图找到x的最小值，这样我的图就不包含任何正权重的回路。 我的问题是——这可能很愚蠢，但我不明白如何——：我如何使用改良的贝尔曼-福特来检查正电路而不是负电路的存在？ 谢谢。
-
我知道Dijkstra算法只能用于边的正长度，而Bellman Ford算法也可以用于图的负长度。 假设我们有一个只有正边的图。贝尔曼·福特会给出和迪克斯特拉一样的结果吗？
-
我在试图理解这个算法是如何工作的。 给定一个问题，搜索从源s到图中所有顶点的路径， 我想我必须这样做： 我的问题是: 我的程序是好的还是我必须改变它。 当我必须检查是否存在负循环时？非常感谢。
-
我知道Bellman-Ford算法适用于有向图。它对无向图有效吗？看起来，对于无向图，它将无法检测循环，因为平行边将被视为循环。这到底是真是假？算法可以应用吗？
-
好的，我发布这个问题是因为这个练习： 我们能否修改Dijkstra的算法，通过变极小为极大来解决单源最长路问题？如果是，那么证明你的算法是正确的。如果没有，那么提供一个反例。 将距离数组初始化为minint 将更改为 然后我做了一些研究来验证我的答案。我发现了这个帖子： 从源到DAG中某些节点之间的最长路径