我们可以在修改后的图上运行 Dijkstra 算法并减去增加的权重以获得原始距离吗？

Question

考虑以下策略，将带有负边缘的图形转换为没有负边权重的图形。令图中的最大幅度负重量为-k。然后，对于具有重量W的图表中的每个边缘，将重量更新为W K 1。考虑以下主张：

要解决原始图中的最短路径问题，我们可以在修改图上运行Dijkstra的算法并减去附加的权重以获取原始

索赔一般不正确

所有图表都是正确的

对于连接的无环图，索赔是正确的

对于带有周期的连接图，索赔通常是不正确的。

Answer 1

一般不正确：考虑带有节点A，B，C和Arcs A-> B，A-> C，B-> C的图形，重量为1,1，-1以该顺序。从A到C的最短路径为A-> B-> C，重量为0。您的策略在所有权重中增加了两个，使A-> C缩短（重量3）。