问题标签 [bellman-ford]

我很难想象 Bellman-Ford 算法是如何纯粹通过阅读代码来工作的。有谁知道使用该算法通过实际图形工作的视觉示例（视频，幻灯片）？谢谢！

我有一个关于贝尔曼福特算法的问题。我创建了这个程序，当给定一个图形时，它将输出源节点和所有其他节点之间的最短距离。那部分工作得很好，所以我有这样的输出：

因此，例如，我的源和节点 2 之间的最短距离是 6，这很棒。但现在我想获得实际路线，而不仅仅是他们的成本。就像从 s 到 v 的路线上的成本不是 5 一样，我想要路线是 s-> b -> v 之类的东西。使用 bellman ford 是否有可能，还是我错过了其中的一部分？

非常感谢。

我有一张像树一样的图表（见下面的粗图。不幸的是无法发布图片）。这是一个 DAG，所有的边都应该指向右边。所有上升的边都将具有负权重，所有下降的边将具有正权重。图表的直径将为 48，但高度可能限制为 5、7 或其他，具体取决于场景。

我想在 48 个节点之后找到从起始节点到最后一个节点的最长路径。经过一些研究，似乎我可以否定所有值（* -1），使用 Bellman-ford 找到最短路径，这应该给我线性时间最长的路径？（http://courses.engr.illinois.edu/cs473/sp2011/lectures/04_class.pdf第 37/40 页）

我知道如果你否定边缘，如果它们最初都是积极的，它应该工作。但是，如果其中一些是正面的而其中一些是负面的，这仍然适用吗？

我的图表是通过以下方式实现的：

节点是节点的向量。每个节点都包含其 ID 和所有邻居（它指向的节点）ID 的向量

有没有办法可以应用 Dijkstra 算法或 Bellman-Ford 来找到两个节点之间的最短路径？找到重复循环？我该怎么做？

编辑：结构意外命名相同。

我对此有一个后续问题： 在最多包含两个负边的图中找到最短路径距离

Ranveer 的解决方案看起来不错，但速度不够快，因为我需要 O(|E| + |V|*log|V|) 快速算法。

我猜杜克林的解决方案效果很好。这是有道理的，它的运行时间与 Dijkstra 算法的运行时间相同。

但是，我的目标是找到从给定节点 s 到 V 中所有节点的最短路径距离。如果我通过将 V 中的所有节点设置为结束顶点 e 来应用 Dukeling 算法，我将需要运行它 |V| - 1 次。那么，运行时间将是 O(|V||E| + |V^2|*log|V|)。

任何帮助，将不胜感激！

我正在做一个任务，它需要一些图形，向图形添加一个额外的顶点，将新顶点作为源应用 Bellman Ford，然后使用将 Dijkstra 的所有对应用于图形。

正在使用的算法具有以下运行时间/空间要求：

如果我在计算整个过程的大 O，我很难理解。每个程序都是单独运行的，并且输出从一个程序传送到另一个程序。我的想法是总算法的 Big-O 运行时间为：

O( V + EV + EV log V )这将简化为O( EV log V )

空间需求将以类似的方式计算。我在想这个正确吗？谢谢！

我必须将Bellman-Ford 算法应用于外汇汇率的最短路径问题 。我正在使用 PHP。起初我以为我会以数组的形式处理数据。但后来我意识到使用数组并不是数据结构的好选择，因为我从 API 获取数据（以 json 类型返回）。

任何人都可以给我一些关于构建数据的想法吗？（我将使用费率、货币符号等）。

这是我处理数据获取的代码（预处理->我选择使用数组，在跳转到贝尔曼福特算法之前）：

但是，我不知道如何获得其他货币之间的汇率（例如 CAD 到 SGD）。我的意思是，我知道如何手动操作。但是货币的数量是 166。当然，我们不想手动这样做。
或者，我是否选择了错误的数据结构？
这是 JSON 中的数据：

而且我还想将数据描述成图表，我应该继续使用数组吗？

问题是这样的：给定一个有向图 G = (V,E)，两个顶点 s,t 和两个权重函数 w1, w2。G 中没有负加权循环（w1 和 w2）。我需要描述一种算法，在给定的从 s 到 t 的最短路径s中，通过 w2 找到从 s 到 t 的最短路径。

我发现了这个： 查找两个顶点之间的所有最短路径 ，但答案对我来说似乎很模糊。

我不知道如何解决这个问题（即使是蹩脚的）。任何帮助，将不胜感激。

我们知道 Bellman Ford 是一种寻找负循环的算法。这是 Bellman Ford 的算法 输入：给定图 G(V,E)，w(e) 是权重 输出：如果存在负循环，则返回 Yes。

第 8 行 - 第 11 行是为了检测负循环而再做一次放松，但是如果图中有一条线，为什么这些行可以保证检测到负循环？

我的 computePaths() 方法中有一个空指针异常，请帮我找出原因。下面是我的代码，我的代码下面是我的输出

顶点类：

边缘类：

算法类：

这是我的输出

所以第 50 for(Edge e : u.adjacencies)行是第 106 行是computePaths(a,vertices);