我正在写关于最短路径算法的论文。而且我不明白一件事...
我已经对 dijkstras 算法进行了可视化。1) 正确吗？还是我做错了什么？2) Bellman-Ford 算法的外观如何？就我寻找差异而言，我发现“Bellman-ford：基本思想与 Dijkstra 的非常相似，但不是选择最短距离的相邻边，而是选择所有相邻边。” 但 dijkstra 也会检查所有顶点和所有边，不是吗？
问问题
19416 次
2 回答
7
dijkstra 假设路径的成本是单调增加的。再加上有序搜索（使用优先级队列），当你第一次到达一个节点时，你是通过最短路径到达的。
这不适用于负权重。如果您使用带负权重的 dijkstra，那么您可能会发现后面的路径比前面的路径更好（因为负权重在后面的步骤中改进了路径）。
所以在贝尔曼福特，当你到达一个节点时，你会测试新路径是否更短。相反，使用 dijkstra，您可以剔除节点
在某些（大多数）情况下，dijkstra 不会探索所有完整路径。例如，如果 G 只链接回 C，那么任何通过 G 的路径都会比通过 C 的任何路径的成本更高。bellman-ford 仍然会考虑通过 G 到 F 的所有路径（dijkstra 永远不会考虑那些，因为它们的成本更高通过 C)。如果它不这样做，它就不能保证找到负循环。
这是一个例子：上面从不计算路径AGEF。当您从 G 到达时，E 已被标记为已访问。
于 2012-05-11T11:46:48.157 回答
2
我也有同样的想法
当所有边都具有非负权重时，Dijkstra 算法解决了单源最短路径问题。它是一种贪心算法，类似于 Prim 的算法。算法从源顶点 s 开始，它会生成一棵树 T，它最终跨越从 S 可达的所有顶点。顶点按距离顺序添加到 T，即首先是 S，然后是最接近 S 的顶点，然后是下一个最近的顶点， 等等。
于 2012-11-16T05:32:04.470 回答