加倍边权后的最短路径

Question

假设我们有一个加权有向图G，我们使用A*搜索或任何其他最短路径算法找到了顶点u和v之间的最短路径。现在假设我们将G中的所有边权重加倍。最短路径是否会改变？

我的论点如下：最短路径不会改变。称原始路径为P，并假设存在第二条不同的从u到v的路径P'，在将边的权重加倍后，P'比P更短。那么，

    weight(P') < weight(P)

在加倍之后，路径P仍然是最短的。然而，如果我们将两边都除以2，我们可以发现在加倍之前路径P'也必须更短，因此P并不是最短路径，我们产生了矛盾。因此，在将边权值加倍后，路径P仍然是最短的。

有人能否对这个解决方案进行评论？它是否正确？

- Ryan

Answer 1

是的，最短路径保持不变。将线性变换应用于边权重不会改变最短路径，只要您不否定边权重。

- Ryan

---

我认为可能有点言过其实了......将每条边的权重乘以正常数因子不会改变最短路径 - 这是正确的（因为乘法对于加法具有分配律）。然而，将每条路径边界加1，也是一种“线性变换”，将对那些含有更多段的路径进行更严厉的惩罚，这通常意味着存在不同的最短路径...... - twalberg

@twalberg 将每个权重加1更恰当地描述为“仿射”，但我同意这里的措辞还有待改进。 - David Eisenstat

@DavidEisenstat 嗯...是的，我相信你是对的...已经有几年了...自从我上次完全掌握线性代数概念以来，我的词汇量有点下降。但如果区别在于线性与高阶多项式、指数、超越函数等方面，那么将仿射变换归为“线性”范畴并不太离谱... - twalberg