我们可以 运行 Dijkstra's algorithm on the modified graph and subtract the added weights to get the original distances?

Question

考虑以下策略，将具有负边权重的图转换为不具有负边权重的图。令图中最大幅度的负边权重为-k。然后，对于图中权重为 w 的每条边，将权重更新为 w+k+1。考虑以下声明：

为了解决原图中的最短路径问题，我们可以运行修改图上的Dijkstra算法，减去增加的权重得到原图

一般情况下该说法不正确

声明对所有图表都是正确的

连通无环图的声明是正确的

对于带环的连通图，该说法通常不正确。

Answer 1

一般情况下不正确：考虑具有节点 A、B、C 和弧 A->B、A->C、B->C 的图，权重依次为 1,1,-1。从 A 到 C 的最短路径是 A->B->C，权重为 0。您的策略将所有权重加二，使 A->C 更短（权重为 3）。