在这种情况下我们能用Dijkstra吗

Question

给定一个具有负权重的图，但我们确信它没有负循环：

将一个足够大的常数添加到所有权重，使它们现在为正，并使用Dijkstra的算法找到最小的路径。

如果我们没有负循环，上面的内容正确吗？如果我们有负循环，我们就不能使用该算法，因为它需要重新访问标记为已完成的节点Dijkstra。

Answer 1

通过在所有权重中添加一个常数，您将使边数较多的路径成本更高，而边数较少的路径成本相对较低，从而中断最初的问题。

因此，即使没有负重量循环，你也不能应用Dijkstra。