贝尔曼福特vs迪克斯特拉：在什么情况下贝尔曼福特会更好？
经过大量谷歌搜索，我发现大多数消息来源说迪克斯特拉算法比贝尔曼-福特算法“更有效”。但是在什么情况下Bellman-Ford算法比Dijkstra算法更好呢？
我知道“更好”是一个宽泛的说法，所以具体来说，我指的是速度和空间，如果适用的话。当然，在某些情况下，贝尔曼-福特方法比迪克斯特拉方法更好。
共有3个答案
唯一的区别是Dijkstra的算法不能处理Bellman ford处理的负边权重。bellman ford还告诉我们图表是否包含负循环。若图形不包含负边，那个么Dijkstra的总是更好。
Bellman-ford的一个有效替代方案是使用拓扑排序的有向无环图（DAG）。
http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/
如所选答案中所述，Bellman-Ford对所有顶点进行检查，Dijkstra只对迄今为止计算出的最佳距离的顶点进行检查。再次指出，这提高了Dijkstra方法的复杂性，但是它需要比较所有顶点以找出最小距离值。由于这在Bellman-Ford中不是必需的，因此在分布式环境中更容易实现。这就是为什么它被用于距离矢量路由协议（例如，RIP和IGRP），其中主要使用本地信息。相反，要在路由协议中使用Dijkstra，首先需要分发整个拓扑，这就是在链路状态协议中发生的情况，例如OSPF和ISIS。
Bellman-Ford算法是一种单源最短路径算法，因此当边权重为负时，它可以检测图中的负循环。
两者之间的唯一区别是Bellman Ford也能够处理负权重，而Dijkstra算法只能处理正权重。
来自维基
然而，Dijkstra算法贪婪地选择尚未处理的最小权重节点，并在其所有输出边上执行此松弛过程；相比之下，Bellman-Ford算法只是简单地放松了所有的边缘，并做到了这一点| V |− 1次，其中| V |是图中的顶点数。在每一次重复中，具有正确计算距离的顶点数量都会增加，因此最终所有顶点都将具有正确的距离。该方法允许Bellman–Ford算法应用于比Dijkstra更广泛的输入类。
然而，在没有负权重边的情况下，Dijkstra通常被认为更好，因为典型的二进制堆优先级队列实现具有O（（|E||V|）log|V|）时间复杂度[Fibonacci堆优先级队列给出O（|V|log|V||E|）]，而Bellman-Ford算法的复杂度为O（|V||E|）
-
我知道Bellman-Ford算法最多需要| V |-1次迭代才能找到最短路径，如果图不包含负权重循环。有没有办法修改Bellman-Ford算法，使其在1次迭代中找到最短路径？
-
我这里有一个更聪明的贝尔曼福特版本： 有人能想到一种图，对于这种图，该算法的时间复杂度下限为（V*E），其中V=#顶点，E=#边 我想看看这个陷阱在哪里。
-
我有一个家庭作业来实现贝尔曼·福特的算法，并在一些图形上测试它。我实现了这个算法，在3张图中的2张上测试了它，它是有效的。但是在第三个图中，我在调用函数时没有输出。 此部分创建图形及其边。函数将顶点数和边数作为参数。 这是添加新边的函数。 下面是我对Bellman Ford算法的实现。
-
在具有V节点和E边的有向图中，Bellman-Ford算法将每个顶点（或者更确切地说，每个顶点的边）松弛（V-1）次。这是因为从源到任何其他节点的最短路径最多包含（V-1）条边。在第V次迭代中，如果边可以松弛，则表示存在负循环。 现在，我需要找到被这个负循环“摧毁”的其他节点。也就是说，由于从源到位于负循环中的节点的路径上有一个或多个节点，因此一些不在负循环中的节点现在与源的距离为负无穷远。 实现
-
我一直试图通过以下资源来理解贝尔曼福特的正确实现：1 如果我们已经知道给定的加权有向图不包含一个圈（因此也没有负圈），是否遵循Bellman-Ford算法的正确实现？ 我在上述实现中遇到的第一个问题是，如果图中只有两个节点具有从源节点到目标节点的定向边，那么需要修改for的第一个
-
我正在努力改进Bellman-Ford算法的性能，我想知道改进是否正确。 我运行松弛部分不是V-1而是V次，并且我得到了一个涉及的布尔变量，如果在外循环的迭代过程中发生任何松弛，则将其设置为。如果在n.迭代中没有发生松弛，其中n 我认为这可能会改善运行时，因为有时我们不必迭代V-1次来找到最短路径，而且我们可以更早地返回，而且它也比用另一块代码检查循环更优雅。