Dijkstra 与 BellFord 算法

Question

如果我需要找到从一个源到图中所有其他顶点的最短路径，既有向又有权，我可以使用 Dijkstras 算法还是需要使用 BellFord 算法？

Answer 1

由于 Dijkstra 的正确实现比 Bellman-Ford 更快，除非图中有负权重边，否则请使用 Dijkstra。在这种情况下，Dijkstra 可能是不正确的，但 Bellman-Ford 仍然会 return 正确答案。

请记住，如果图具有负权重循环，则最短路径未明确定义。可以修改 Bellman-Ford 以能够检查给定图形是否具有负权重循环。