问题标签 [bellman-ford]

我使用矩阵d来呈现图表。表示和d.(i).(j)之间的距离；表示图中的节点数。ijv

该图中可能存在负循环。

我想检查是否存在负循环。我从Floyd-Warshall的变体中写了如下内容：

我的问题是

1. 上面的代码正确吗？
2. part 1有用吗？

因为我经常调用这个函数，所以我真的想让它尽可能快。所以我的 3) 问题是其他算法（尤其是Bellman-Ford）是否可以比这更快？

我在看Floyd-Warshall 算法。

在页面中，它说the Floyd–Warshall algorithm assumes that there are no negative cycles。所以我的问题是如果入口图隐藏了负圆会发生什么。输出会dist代表另一个隐藏负圆的图吗？这不part 1无效吗？

经过大量谷歌搜索，我发现大多数消息来源都说 Dijkstra 算法比 Bellman-Ford 算法“更有效”。但是在什么情况下，Bellman-Ford 算法优于 Dijkstra 算法呢？

我知道“更好”是一个宽泛的说法，所以我特别指的是速度和空间（如果适用的话）。在某些情况下，Bellman-Ford 方法肯定比 Dijkstra 方法更好。

我偶然发现了我最初从Wikipedia获得的著名 Yen 对 Bellman-Ford 算法的优化，然后我在练习部分的几本教科书中发现了相同的改进（例如，这是 Cormen 中的问题 24-1 和Sedgewick 中的Web 练习 N5 ）算法”）。

这是改进：

Yen 的第二个改进首先在所有顶点上分配一些任意线性顺序，然后将所有边的集合划分为两个子集。第一个子集 Ef 包含满足 i < j 的所有边 (vi, vj)；第二个，Eb，包含边 (vi, vj)，使得 i > j。每个顶点按 v1、v2、...、v|V| 的顺序访问，从 Ef 中的该顶点放宽每个出边。然后以 v|V|、v|V|-1、...、v1 的顺序访问每个顶点，从 Eb 中的该顶点放宽每个出边。算法主循环的每次迭代，在第一次迭代之后，将至少两条边添加到松弛距离与正确最短路径距离匹配的边集：一条来自 Ef，一条来自 Eb。这种修改减少了算法主循环的最坏情况迭代次数 |V| − 1 到 |V|/2。

不幸的是，我没有找到这个界|V|/2的证明，而且，我似乎找到了一个反例。我确定我错了，但我看不出具体在哪里。

反例只是一个路径图，其顶点标记为 1 到 n，初始顶点为 1。（因此，对于 i 在 1 到 n-1 的范围内，E={(i, i+1)}）。在这种情况下，前向顶点集等于 E (E_f = E)，而后向顶点集只是空集。算法的每次迭代仅添加一个正确计算的距离，因此算法在 n-1 时间内完成，这与建议的边界 n/2 相矛盾。

我究竟做错了什么？

UPD：所以这个错误非常愚蠢。我没有考虑通过顶点的迭代，而是将迭代视为路径成本的即时更新。我不会删除这个话题，因为有人赞成它，以防这种改进对某人来说很有趣。

Dijkstra 的算法比 bellman 算法更有效，我们仍然使用 bellman ford 算法来表示负边，但是这些负边在网络中甚至代表什么？我在任何地方都找不到这个问题的答案，这个问题让我很生气，我只需要一些应用程序，所以我觉得它真的很有用。

关于这个算法有很多问题，但我一直没能找到它如何处理负重量循环？假设路由器 x 从路由器 y 获得更新，y 到 z 的成本为 5。稍后，路由器 x 从路由器 y 获得更新，y 到 z 的成本现在为 2。路由器 x 是做什么的？我的理解是贝尔曼福特算法指出在这种情况下应该提出错误。但是距离矢量路由算法是做什么的——简单地更新它或引发错误或其他什么？

我了解到 Bellman-Ford 算法的运行时间为 O(|E|*|V|)，其中 E 是边数，V 是顶点数。假设该图没有任何负加权循环。

我的第一个问题是，我们如何证明在 (|V|-1) 次迭代中（每次迭代检查 E 中的每条边），在给定特定起始节点的情况下，它会更新到每个可能节点的最短路径？有没有可能我们已经迭代了 (|V|-1) 次，但仍然没有得到到每个节点的最短路径？

假设算法的正确性，我们实际上可以做得更好吗？在我看来，并非所有边在特定图中都具有负权重。Bellman-Ford 算法似乎很昂贵，因为每次迭代都要经过每个边缘。

谁能指出一个简单的并行最短路径算法的良好伪代码？或者任何语言，都没关系。我很难找到好的例子=[

所以我遇到了这个美丽的问题，它要求你编写一个程序来确定有向图中是否存在负无穷最短路径。（也可以认为是查找图中是否存在“负循环”）。这是问题的链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499

我通过从图中的任何源开始运行 Bellman Ford 算法两次成功地解决了这个问题。第二次运行算法时，我检查一个节点是否可以放松。如果是这样，那么图中肯定存在负循环。下面是我的 C++ 代码：

一位教授曾经告诉我，Dijkstra 的最短路径算法找不到这样的负循环，但他没有证明这一点。我实际上怀疑这种说法。

我的问题是，Dijktstra 的单源最短路径算法可以检测到负循环吗？

当然，我可以尝试 Dijkstra 并检查它是否有效，但我很高兴能与您分享这个想法。

我输入了这样的地图：

这是地图的外观：

数组中的字符与每个正方形相对应，也就是说，灰色是 h，这是一块石头，我不能这样走。棕色是正常路径（c），长度为 1 绿色是森林（n），长度为 2

然后是d作为龙和p作为公主，我必须先找到通往龙的最短路径，然后再找到公主，然后返回确切的最短路径..

所以我的第一个问题是，有没有办法把这个输入放到一些修改过的 Dijkstra、Bellman-Ford 或一些不同的算法中？或者我必须首先为每个正方形建立一个连接，从正方形 1,2 我可以到 1,1 并且长度是 2，到 2,2 并且长度是 2，或者我可以简单地通过某种方式运行算法双数组？？

问题 2 您建议使用哪种算法？我想到了贝尔曼福特，虽然我没有负平方，但我需要返回确切的路径，这很容易感谢数组 pi，它在贝尔曼福特中维护，但我愿意接受任何建议，因为我刚刚进入图论。