如何使贝尔曼福特在最坏的情况下运行？
我试图使优化版的贝尔曼福特算法在最坏的情况下运行。优化版我的意思是，如果在放松1轮边后，在最短距离上没有进一步更新，则终止。
例如，一个具有7个顶点的简单连通加权有向图，使得从源顶点0运行优化贝尔曼-福特算法至少使用5轮来获得正确的最短路径。
图表不能包含负权重循环。i、 e.处理顶点0的所有传出边，然后处理顶点1的边，依此类推
我知道这和周期有关。但我不太确定绘制图表的策略是否符合要求。
共有1个答案
您的Bellman-Ford算法版本将需要与图中所有最短路径的最长长度（边）一样多的迭代。
考虑有n个顶点的有向图。将边添加到1-
进一步注意，Bellman-Ford算法有一个改进版本。它被称为最短路径快速算法。尽管它的最坏运行时间是O（|V |*| E |），这与Bellman Ford相同，但很少有图形能够使算法达到该时间。实际上，您可以预期平均运行时间为O（| E |）（未经验证）。
-
经过大量谷歌搜索，我发现大多数消息来源说迪克斯特拉算法比贝尔曼-福特算法“更有效”。但是在什么情况下Bellman-Ford算法比Dijkstra算法更好呢？ 我知道“更好”是一个宽泛的说法，所以具体来说，我指的是速度和空间，如果适用的话。当然，在某些情况下，贝尔曼-福特方法比迪克斯特拉方法更好。
-
我知道Bellman-Ford算法最多需要| V |-1次迭代才能找到最短路径，如果图不包含负权重循环。有没有办法修改Bellman-Ford算法，使其在1次迭代中找到最短路径？
-
我这里有一个更聪明的贝尔曼福特版本： 有人能想到一种图，对于这种图，该算法的时间复杂度下限为（V*E），其中V=#顶点，E=#边 我想看看这个陷阱在哪里。
-
我有一个家庭作业来实现贝尔曼·福特的算法，并在一些图形上测试它。我实现了这个算法，在3张图中的2张上测试了它，它是有效的。但是在第三个图中，我在调用函数时没有输出。 此部分创建图形及其边。函数将顶点数和边数作为参数。 这是添加新边的函数。 下面是我对Bellman Ford算法的实现。
-
我已经成功地实现了Bellman-Ford，当边具有负权重/距离时，找到最短路径的距离。我无法让它返回所有最短路径（当最短路径有联系时）。我设法用Dijkstra获得所有最短的路径（给定的一对节点之间）。贝尔曼-福特有可能吗？（只是想知道我是否在浪费时间）
-
在具有V节点和E边的有向图中，Bellman-Ford算法将每个顶点（或者更确切地说，每个顶点的边）松弛（V-1）次。这是因为从源到任何其他节点的最短路径最多包含（V-1）条边。在第V次迭代中，如果边可以松弛，则表示存在负循环。 现在，我需要找到被这个负循环“摧毁”的其他节点。也就是说，由于从源到位于负循环中的节点的路径上有一个或多个节点，因此一些不在负循环中的节点现在与源的距离为负无穷远。 实现