问题标签 [bellman-ford]

我对 JS 很陌生，我的一个朋友给我发了这个小提琴

（最短路径 Bellman-Ford）并且不明白为什么它会property 'length' of undefined在控制台中引发错误。

任何建议如何解决此错误？

我有一个 Bellman - Ford 算法的实现。输入程序提供了一个边列表。没有优化它看起来像这样：

它具有 O(V * E) 的复杂性，但通过优化，他的工作速度非常快。看起来像

在实践中，如果外部循环中的顶点数（例如一万个）只有 10-12 次迭代而不是 1 万次，那么算法就完成了它的工作。

这是我的生成代码：

但是我需要生成一个图表，在这个图表上完成他的工作不会那么快。那可以在生成器中更改吗？

我们有一个有 100 个顶点的有向图。v1 --> v2 --> ... v100 并且所有边的权重都等于 1。我们想使用 bellman-ford 来查找从 v1 到其他顶点的所有最短路径。该算法在每一步中以任意顺序检查所有边。如果在每一步中到所有其他顶点的最短距离 v1 没有改变，则该算法停止。步数与检查边的顺序有关。这个问题的最小和最大步数是多少？

解决方案：2 和 100。

我认为：

如果我们有这个图：v1->v2->v3->...->v100，我们需要 2。如果我们有 V1->v2，V1->V3，V1->V4，...我们需要 100。最后，如果我们有 v99v100,v98v99,...,v3v2,v2v1，我们再次需要 100。

任何人都可以帮助或验证我吗？

当我在Algorithms, 4th edition, Robert Sedgewick and Kevin Wayne一书中遇到以下问题时，我最近正在了解最短路径算法。

假设我们通过在 EdgeWeightedDigraph 中为 EdgeWeightedGraph 中的每个 Edge 创建两个 DirectedEdge 对象（每个方向一个）将 EdgeWeightedGraph 转换为 Directed EdgeWeightedGraph，然后使用 Bellman-Ford 算法。解释为什么这种方法会失败。

下面是我实现贝尔曼福特算法（基于队列）的一段代码：

我在纸上尝试了许多示例，但无法找到生成的有向图将在其中包含新的负循环的场景，只需将一条边转换为相反方向的两条边即可。我假设在未加权的无向边加权图中没有预先存在的负循环。

哪个 python 包实现了 Bellman-Ford 最短路径算法？

给定一个起始节点 i 和一个具有负权重的邻接矩阵 G，我想找到从 i 到另一个节点 j 的最短路径。例如，我的图表如下所示：

我只能找到一个全对最短路径实现，这对于我的需求来说似乎太浪费了，因为我的图很大，我只需要一对节点的最短路径。性能对我来说很重要，因为我会将它用于数千个图表。

因此，我正在四处寻找贝尔曼福特的实施——有人见过吗？

Given 是一个无向的加权图。每个节点要么是一个“城市”，要么是一个“村庄”；节点通过边（=道路）连接。

我从节点 1 开始，必须向所有城市传达信息。在某人到达的每个城市中，任意数量的人都可以帮助传播信息（这样他们就可以开始开车到另一个节点）。

我现在正在寻找必须在道路上行驶的最小距离，以便所有城市都能收到信息。（当 x 人使用特定道路时，它也计算 x 倍边缘权重）

解决方案：我认为，首先在所有城市之间获得最小生成树会很有帮助。但问题是，也有村庄。（-->“施泰纳树问题”）。所以我想有可能用 Dijkstra 或 Bellman-Ford 以某种方式解决它；还是最短路径和MST的组合？

你们有什么想法吗？我不需要代码，但只是一个基本的想法如何解决这个问题会非常有帮助:) 谢谢。

所以我试图使用修改后的贝尔曼福特算法来找到从起始顶点到结束顶点的最短路径，但我不能超过一定的距离。所以给定一个带边的图：

其中每条线代表一条边，第一个值是起始顶点，第二个值是结束顶点，第三个是成本，第四个是距离。使用我现在拥有的代码，当我尝试找到从 0 到 3 的最便宜路径而不超过 140 时，它会产生 0（未找到路径时的默认值）而不是 340（最便宜路径的成本）。有关如何更改我的代码的任何建议。

只需将代码复制到下面，因为该站点不允许我做任何其他事情。

请帮忙！这可能不是那么难，但决赛让我压力山大

所以给定初始和最终节点，我需要使用 Bellman-Ford 算法来：

1. 找到一条成本最低的路径，同时

2. 停留在特定时间段内

每条边都有成本和时间/持续时间权重。

但是，我不知道如何优化它，也许是优先级队列？我会改变放松功能还是整个程序？

我一直在搜索贝尔曼福特算法的空间复杂度，但在维基百科贝尔曼福特算法上，它说空间复杂度是 O(V)。在这个链接上它说 O(V^2) 。我的问题是；什么是真正的空间复杂度，为什么？

我试图找出在 Java 中实现加权有向图的最佳方法，以便我可以将 Bellman-Ford 上的运行时间保持在 |V|*|E|。基本上我的问题是如何表示图中的边缘。

我已经看到了邻接矩阵的使用，但我似乎无法弄清楚如何使用邻接矩阵同时保持运行时间低于 O(V^2)。我得到 V^2 作为运行时间的原因是因为 Bellman-Ford 要求我们遍历所有边，但它为了获取边列表，我需要遍历整个矩阵以获取所有边。无论如何，使用邻接矩阵可以获得比 O(V^2) 时间更快的边列表吗？

还是我需要使用邻接列表？