algorithm - 即使在具有负边权重的图中，我们能否使用 Dijkstra 找到最短路径？

Question

假设我有一个图，其中最小边权重为 −100。我可以将 100 作为所有边的偏移量并使用 Dijkstra 算法吗？

请帮助我理解为什么这样的方法会给出错误的解决方案。

Answer 1

将 100 添加到每个边权重会给出错误的解决方案，因为它对边数较多的路径的惩罚要大于对边数较少的路径的惩罚。

例如，假设我们有一个图，从 A 点到 B 点的最短路径有 3 条边，总距离为 5。假设从 A 点到 B 点的另一条路径有 2 条边，但总距离为 10 .

如果我们将每条边的权重加 100，则第一条路径的成本为 305，而第二条路径的成本为 210。因此第二条路径变得比第一条路径短。

因此，我们可以得出结论，为每个边权重添加偏移量或偏差并不一定能保持最短路径。