DIjkstra和BellmanFord算法之间的区别

我正在为最短路径算法提供论文。而我不明白一件事... enter image description here DIjkstra和BellmanFord算法之间的区别

我已经使dijkstras算法的可视化。 1）它是正确的吗？或者我做错了什么？ 2）如何看贝尔曼福特算法？就像我寻找差异一样，我发现“Bellman-ford：基本思想与Dijkstra非常相似，但不是选择最短距离的相邻边缘，而是选择所有相邻边缘。”但是dijkstra也检查所有顶点和所有边，不是吗？

来源

2012-05-11 Wish

IFRC贝尔曼 - 福特管理也带负成本 – BigMike

但是，如果我想为bellman-ford做这样的可视化，它会看起来一样吗？ – Wish

您可以用负值显示不同图形的B-F。但对于迪克斯特拉你不能使用它。 – shan

dijkstra假定路径的成本是单调增加的。加上有序搜索（使用优先级队列），当你第一次到达一个节点时，你已经通过最短路径到达了。

负面权重并非如此。如果你使用负权重的dijkstra，那么你可能会发现后面的路径比前面的路径好（因为负权重改善了后面的路径）。

所以在bellman-ford中，当你到达你测试的节点时，看看新路径是否更短。与dijkstra相反，您可以在某些（大多数）情况下剔除节点

dijkstra不会探索所有完整路径。例如，如果G仅链接到C，那么通过G的任何路径的成本都较高，因此通过C. bellman-ford的所有路径仍然会考虑通过G到F的所有路径（dijkstra从不会看这些，因为它们的成本较高通过C）。如果它不这样做，它不能保证找到负循环。

这里有一个例子：上面从不计算路径AGEF。 Ë已经被打上了你G.

来源

2012-05-11 11:46:48

我还想到同样

Dijkstra算法到达的时间，走访解决了单源最短路径问题，当所有的边有非负的权重。它是一种贪婪算法，与Prim算法类似。算法从源顶点s开始，它生长一棵树T，最终跨越从S到达的所有顶点。顶点按照距离的顺序被添加到T，即，首先S，然后是距离S最近的顶点，然后是第二近的顶点，等等。

来源

2012-11-16 05:32:04 PALLAVI

DIjkstra和BellmanFord算法之间的区别

回答

相关问题