我正在撰写有关最短路径算法的论文，但有一点我不理解...
我已经制作了Dijkstra算法的可视化图形。 1）这个图是正确的吗？还是我做错了什么？ 2）贝尔曼-福德算法会是什么样子？就我所知道的区别而言，“Bellman-ford：基本思想与Dijkstra's非常相似，但它选择所有相邻边缘，而不是选择最短距离相邻边缘。” 但是dijkstra也会检查所有顶点和所有边，不是吗？
Dijkstra算法和Bellman-Ford算法的区别
14
- Wish
4
4IFRC Bellman-Ford算法也可以处理边具有负权值的情况。 - BigMike
但是如果我想要制作像这样的可视化效果，比如Bellman-Ford算法，它看起来会一样吗？ - Wish
2你可以使用带有负值的不同图形来可视化B-F算法，但是对于Dijkstra算法则不行。 - shan
更适合理论计算机科学的软件工程。 - djechlin
2个回答
7
迪科斯彻算法假定路径的成本是单调递增的。加上有序搜索（使用优先队列），这意味着当你第一次到达一个节点时，你已经通过最短路径到达了那里。
但是，如果有负权重，则这种情况并不成立。如果您在带有负权重的迪科斯彻算法中使用，则可能发现后面的路径比前面的更好（因为负权重在后续步骤中改进了路径）。
因此，在Bellman-Ford算法中，当您到达节点时，请测试新路径是否更短。相比之下，使用迪科斯彻算法时，您可以剔除节点。
在某些（大多数）情况下，迪科斯彻算法将不会探索所有完整的路径。例如，如果G仅链接回C，则通过G的任何路径都比通过C的路径成本更高。Bellman-Ford仍然会考虑通过G到F的所有路径（迪科斯彻永远不会查看它们，因为它们的成本比通过C更高）。如果没有这样做，就无法保证发现负循环。
以下是一个示例：上述示例从未计算路径AGEF。当您从G到达时，E已被标记为“已访问”。
但是，如果有负权重，则这种情况并不成立。如果您在带有负权重的迪科斯彻算法中使用，则可能发现后面的路径比前面的更好（因为负权重在后续步骤中改进了路径）。
因此，在Bellman-Ford算法中，当您到达节点时，请测试新路径是否更短。相比之下，使用迪科斯彻算法时，您可以剔除节点。
在某些（大多数）情况下，迪科斯彻算法将不会探索所有完整的路径。例如，如果G仅链接回C，则通过G的任何路径都比通过C的路径成本更高。Bellman-Ford仍然会考虑通过G到F的所有路径（迪科斯彻永远不会查看它们，因为它们的成本比通过C更高）。如果没有这样做，就无法保证发现负循环。
以下是一个示例：上述示例从未计算路径AGEF。当您从G到达时，E已被标记为“已访问”。
- andrew cooke
2
我也有同样的想法。
Dijkstra算法解决的是所有边都为非负权重的单源最短路径问题。它是一种贪心算法，与Prim算法相似。该算法从源顶点s开始，生成一棵树T，最终覆盖所有可从S到达的顶点。顶点按距离顺序添加到T中，即先S，然后是最靠近S的顶点，接下来是次近的，以此类推。
- PALLAVI
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接