日元对贝尔曼福特的改善
我一开始从维基百科上得到著名的颜教授对Bellman-Ford算法的优化，后来我在几本教科书的练习部分发现了同样的改进（例如，这是Cormen中的24-1问题和Sedgewick的“算法”中的网络练习N5）。
以下是改进：
Yen的第二个改进首先在所有顶点上指定一些任意的线性顺序，然后将所有边集划分为两个子集。第一个子集Ef包含所有边（vi，vj），因此i
不幸的是，我没有找到这个界| V |/2的证明，而且，我似乎找到了一个反例。我肯定我错了，但我看不出确切的位置。
反例是一个路径图，其顶点标记为1到n，初始顶点为1。（因此，E={（i，i 1）}表示i在1到n-1范围内）。在这种情况下，前向顶点集等于E（E_f=E），后向顶点集只是空集。算法的每次迭代只增加一个正确计算的距离，因此算法在n-1时间内完成，这与所提出的界n/2相矛盾。
我做错了什么？
UPD：所以这个错误非常愚蠢。我没有考虑通过顶点的迭代，而是考虑迭代作为路径成本的即时更新。我不会因为有人投票赞成而删除这个话题，以防这种改进对某人来说很有趣。
共有1个答案
这实际上是最好的情况，它在2次迭代中完成，而不管顶点的数量。
在纸上绘制迭代或编写代码。第一次迭代将找到所有正确的最短路径。然后，第二次迭代将不会改变任何内容，算法将终止，因为上一次迭代改变了距离的顶点集是空的。
“向前”运行通过松弛Ef边集的顶点将完成所有工作，而“向后”运行不会完成任何工作，因为Eb是一个空集。
-
我知道Bellman-Ford算法最多需要| V |-1次迭代才能找到最短路径，如果图不包含负权重循环。有没有办法修改Bellman-Ford算法，使其在1次迭代中找到最短路径？
-
我正在努力改进Bellman-Ford算法的性能，我想知道改进是否正确。 我运行松弛部分不是V-1而是V次，并且我得到了一个涉及的布尔变量，如果在外循环的迭代过程中发生任何松弛，则将其设置为。如果在n.迭代中没有发生松弛，其中n 我认为这可能会改善运行时，因为有时我们不必迭代V-1次来找到最短路径，而且我们可以更早地返回，而且它也比用另一块代码检查循环更优雅。
-
我这里有一个更聪明的贝尔曼福特版本： 有人能想到一种图，对于这种图，该算法的时间复杂度下限为（V*E），其中V=#顶点，E=#边 我想看看这个陷阱在哪里。
-
我有一个家庭作业来实现贝尔曼·福特的算法，并在一些图形上测试它。我实现了这个算法，在3张图中的2张上测试了它，它是有效的。但是在第三个图中，我在调用函数时没有输出。 此部分创建图形及其边。函数将顶点数和边数作为参数。 这是添加新边的函数。 下面是我对Bellman Ford算法的实现。
-
在具有V节点和E边的有向图中，Bellman-Ford算法将每个顶点（或者更确切地说，每个顶点的边）松弛（V-1）次。这是因为从源到任何其他节点的最短路径最多包含（V-1）条边。在第V次迭代中，如果边可以松弛，则表示存在负循环。 现在，我需要找到被这个负循环“摧毁”的其他节点。也就是说，由于从源到位于负循环中的节点的路径上有一个或多个节点，因此一些不在负循环中的节点现在与源的距离为负无穷远。 实现
-
经过大量谷歌搜索，我发现大多数消息来源说迪克斯特拉算法比贝尔曼-福特算法“更有效”。但是在什么情况下Bellman-Ford算法比Dijkstra算法更好呢？ 我知道“更好”是一个宽泛的说法，所以具体来说，我指的是速度和空间，如果适用的话。当然，在某些情况下，贝尔曼-福特方法比迪克斯特拉方法更好。