问题标签 [bellman-ford]

嘿，我一直在研究“单源最短路径”问题的贝尔曼福特算法。

现在我被困在一个点上，我需要找出具有负权重循环的图形的解决方案。

但是贝尔曼福特算法在这里不起作用。

有人可以建议我该怎么做。如何解决负重循环的问题？

谢谢你的时间。

我在这里有一个更智能的 Bellman-Ford 版本：

谁能想到这种算法的下限为 (V*E) 时间复杂度的图类型，其中 v = #vertices, E = #edges

我想看看这其中的陷阱在哪里。

我对 Bellman-Ford 进行了轻微的修改，使它只做“有用的”放松。也就是说，更新了意味着 d(v) 的松弛。

现在，如果所有最短路径最多有 k 个弧。那么最坏情况的运行时间是 O(V*k)，因为我们在这个智能版本中只经过 k 个弧。这比原来的 O(V*E) 快一点，因为 |k| < |E|

谁能告诉我这种改进版本不比原来的 Bellman-Ford 算法更好的图类型？也就是说，最佳情况下的性能是 O(V*E)

在 Dijkstra 的最短路径算法和其他算法中，检查边以查看它是否提供到节点的更好路径被称为松弛边。为什么叫放松呢？

当边缘具有负权重/距离时，我已成功实施 Bellman-Ford 以找到最短路径的距离。我无法让它返回所有最短路径（当有最短路径时）。我设法用 Dijkstra 获得了所有最短路径（在给定的一对节点之间）。Bellman-Ford 有可能吗？（只是想知道我是否在浪费时间尝试）

我一直在研究这三个，我在下面陈述我的推论。有人能告诉我我是否足够准确地理解它们吗？谢谢你。

1. Dijkstra 算法仅在您有单一来源并且您想知道从一个节点到另一个节点的最小路径时使用，但在这种情况下会失败

2. 当所有节点中的任何一个都可以成为源时，使用 Floyd-Warshall 算法，因此您希望从任何源节点到任何目标节点的最短距离。这仅在存在负循环时才会失败

（这是最重要的一个。我的意思是，这是我最不确定的一个：）

3.当只有一个来源时，Bellman-Ford 的使用与 Dijkstra 的一样。这可以处理负权重，它的工作方式与 Floyd-Warshall 的相同，除了一个来源，对吧？

如果你需要看一下，对应的算法是（由维基百科提供）：

贝尔曼福特：

迪杰斯特拉：

弗洛伊德-沃歇尔：

在编写 bellman-ford 算法时，我遇到了一个问题，这个问题更多的是理论而不是技术，但这里是：

我有 4 个点 A、B、C、D，从 A 到 B 的成本等于 3 等。这是图表：

假设我想知道从 A 到 C 通过 D 的成本是多少，会是：10？或者它会从 A 到 D（成本为 1）然后从 D 回到 A（总成本为 1+1=2）然后从 A 到 B（1+1+3=5）和从 B 到 C（ 1+1+3+3=8) 所以8不会10？

我到处搜索，但找不到任何合理的答案。

编辑：
假设对于 A->D 和 D->C 路径计数将为 2，对于 A->D 然后 D->A 然后 A->B 然后 B->C 总路径计数等于 4 所以它会选择路径数最短的方式（路径数 = 2）还是较长的方式（路径数 = 4）？

据说，“如果从源可以到达负边缘循环，那么算法将返回错误”。

这个“从源头可达”是什么意思？

看下图：

你能给我一些例子，如果存在从源可以到达的负边缘循环，这个算法将返回 false。

注意：我是算法新手。

我想知道，如果有一个加权图 G(V,E)，并且我需要在其中找到任意两个顶点 S 和 T 之间的一条最短路径，那么我可以使用 Dijkstras 算法。但是我不确定当我们需要找到从 S 到 T 的所有不同的最短路径时如何做到这一点。它是否可以在 O(n) 时间内解决？我还有一个问题，比如如果我们假设图中边的权重只能在某个范围内假设值，比如说 1 <=w(e)<=2 这会影响时间复杂度吗？

我正在尝试为模拟路由器的类编写程序，到目前为止我已经设置了基础知识（“路由器”可以通过模拟服务器向连接到服务器的其他“路由器”发送和接收数据包）。每个数据包仅包含该路由器的距离矢量。当路由器接收到一个数据包时，它应该使用 Bellman-Ford 算法相应地更新它自己的距离矢量。我遇到的问题是我发现自己无法在不作弊和使用邻接矩阵的情况下实现实际算法。

例如，假设我有 3 个路由器连接如下：

也就是说，A 和 B 以链路成本 1 连接，B 和 C 以链路成本 2 连接。所以当路由器都启动时，它们会向每个直接连接的邻居发送一个数据包，其中包含它们的距离矢量信息。所以 A 会发送路由器 B (0, 1, INF)，B 会发送 A 和 C (1, 0, 2)，C 会发送 B (INF, 2, 0)，其中 INF 表示 2 个路由器没有直接连接。

因此，让我们看看路由器 A 从路由器 B 接收数据包。使用 Bellman-Ford 算法计算到其他路由器的最小成本如下。

所以我遇到的问题是，我一生都无法弄清楚如何实现一个算法来计算一个路由器到每个其他路由器的最小路径。如果您确切知道将有多少个路由器，那么制作一个很容易，但是当路由器的数量可以任意大时，您会怎么做呢？