证明重新加权的图具有与以前相同的最短路径

Question

假设 G′ 是使用以下规则从 G 重新加权的图：w′(u,v)=w(u,v)−f(u)+f(v)，其中 f 总是产生任何节点的积极结果。我们能否证明从s到t的最短路径PG仍然是G′中从s到t的最短路径？

Answer 1

考虑一条路径：

P = <v1,v2,v3, ..., v(n-2), v(n-1), vn>

那么路径的权重为：

w(P) = w(v1,v2) + w(v2,v3) + ... w(v(n-2), v(n-1)) + w(v(n-1), vn)

如果重新加权图形，则路径的重新加权值为：

w'(P) = w'(v1,v2) + w'(v2,v3) + ... + w'(v(n-2), v(n-1)) + w'(v(n-1), vn)
      =   w(v1,v2) - f(v1) + f(v2)
        + w(v2,v3) - f(v2) + f(v3)
        + w(v3,v4) - f(v3) + f(v4)
          ...
        + w(v(n-3),v(n-2)) - f(v(n-3)) + f(v(n-2))
        + w(v(n-2),v(n-1)) - f(v(n-2)) + f(v(n-1))
        + w(v(n-1),vn)     - f(v(n-1)) + f(vn)
      = w(P) - f(v1) + f(vn)

注意重新加权因子如何在路径中间抵消并仅应用于端点。

现在给定从 v1 到 vn 的所有路径的集合，然后根据您提供的重新加权公式对路径重新加权将改变所有路径的成本相同的数量（因为端点是相同的，并且重新加权只会根据端点改变路径的成本）。因此，如果这些路径之一是最小成本路径，那么它在重新加权后仍将是最小成本路径。

证明重新加权的图具有与以前相同的最短路径

Proving the re-weighted graph have the same shortest path as before

math

graph-theory