贝尔曼·福特和一个奥运会问题？
三天前我参加了一次奥运会考试。我遇到了一个很好的问题，如下所示。
我们知道bellman-ford算法在每个步骤中检查所有的边，如果，
然后更新d（v），使w（u，v）是边的权重（u，v），d（u）是顶点u的最佳查找路径长度。如果在一个步骤中，没有顶点更新，则算法终止。假设该算法在图G中的n顶点在k之后，从顶点s寻找所有最短路径
来自s的所有最短路径中的边数最多为k-1
谁能讨论这些选择？
共有2个答案
我认为选项3是不正确的，因为要知道是否存在负权重循环，Bellman-ford算法需要运行n次。首先计算n-1次最短路径，然后再检查一次距离是否有任何改进。如果有改进，则表示存在负权重循环。
1是不正确的。首先，我们总是找到有k条边的最短路径，如果有的话。而且，如果我们碰巧按照最短路径树的拓扑顺序放松弧，那么我们在一次迭代中收敛，尽管最短路径树可能是任意深的。
s --> t --> u --> v
Relax s->t, t->u, u->v; shortest path from s->v is three hops,
but B--F has made two iterations.
2是不正确的，因为谁知道重量是多少？
100
s --> t
Relax s->t; weight is 100, but B--F has made two iterations.
3是正确的，因为通过平均参数，负循环中至少有一个弧是不松弛的。让v1。。。，vn是一个循环。因为弧是松弛的，所以我们有d（vi）len（vi）-
-
我知道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次迭代中，如果边可以松弛，则表示存在负循环。 现在，我需要找到被这个负循环“摧毁”的其他节点。也就是说，由于从源到位于负循环中的节点的路径上有一个或多个节点，因此一些不在负循环中的节点现在与源的距离为负无穷远。 实现
-
我一直试图通过以下资源来理解贝尔曼福特的正确实现：1 如果我们已经知道给定的加权有向图不包含一个圈（因此也没有负圈），是否遵循Bellman-Ford算法的正确实现？ 我在上述实现中遇到的第一个问题是，如果图中只有两个节点具有从源节点到目标节点的定向边，那么需要修改for的第一个