我们能否在存在负边权的图中使用Dijkstra算法找到最短路径？

Question

4

假设我有一张图，其中最小边权为-100。我能够给所有的边加上100的偏移量并使用Dijkstra算法吗？

请帮助我理解为什么这种方法会导致错误的解答。

- Pradhan

1

你认为为什么会给出错误的答案？ - bmargulies

1

它给出错误的答案，因为Dijkstra算法不适用于负数，并且Nayuki已经指出了原因。 - nikhil

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nayuki · Accepted Answer

将每条边的权重加100会导致错误的解决方案，因为它惩罚了比那些少一些边的路径，要多一些边的路径。

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

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

Example graph

因此，我们可以得出结论，向每个边权值添加偏移量或常数并不能保证最短路径不变。