dijkstra's vs Bellman-Ford算法

Question

我目前的理解是，dijkstra的算法比贝尔曼-福特算法更有效，只是它不能处理负边缘。然而，假设我们有一个边权重图，其中有负权重的边，图中没有负权重的圈，我们还能使用dijkstra算法吗？

Answer 1

这个问题已经在这里得到了很好的回答。https://stackoverflow.com/a/13159425/12449779

总而言之，Dijkstra的算法在每次迭代中以最小距离标记离“标记”顶点的顶点。最初，源顶点是距离为0的唯一标记顶点。假设存在两个标记顶点A和B，它们与源之间存在一定的有限距离，并且它们的路径不重叠()。当前，到A和B的路径将被认为是从A到B的最短可能路径。由于路径不重叠，因此任何从源到A到B的路径的长度将是Source到A+从A到B的路径的长度，这大于从源到B的路径的长度，因为从源到A和B的路径不重叠。但如果允许负权重边，这不会保持。因为从A到B的路径长度可以是负。因此，Dijkstra的算法不适用于。也没有简单的方法可以将具有负边的一般图转换为具有非负边的图。贝尔曼福特适用于任何不包含负权圈的图。