algorithm - 关于 Dijkstra 算法

Question

这是我的问题。如果某些边权重为负，则可以通过将常数 C 添加到每个边权重来获得从 s 的最短路径，该常数 C 大到足以使所有边权重为非负，并运行 Dijkstra 算法。

这是真的还是假的，为什么？

Answer 1

False ：如果某些边权重为负，则可能没有最短路径。

可以循环进入负成本循环，以尽可能多地降低成本。

就是说，如果你禁止使用两次相同的点，我认为它是正确的。

即使您禁止使用两次相同的点，它仍然不能像 MrSmith42 所说的那样工作：

您可能有两条路径，一条成本为 0+0+0+0+0+0+0+0+0+0=0，一条成本为 10+(-4)=6。如果将所有权重增加 4，则成本将为 4+4+4+4+4+4+4+4+4+4+4=40，其他 14+0=10。这样，通过更改权重，更便宜的路径会变成更昂贵的路径。

Answer 2

您正在更改问题以有效地增加 C * 路径长度的惩罚。

这意味着您可能会根据 C 的值得到不同的答案。

C 越大，您的算法就越倾向于选择从源到目的地的路径，边数最少。

话虽如此，如果您的图表使得从源到目的地的每条路径始终具有相同的长度，那么这种方法将起作用。

这将适用的图表示例