边缘权重加倍后的最短路径

Question

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

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

    weight(P') < weight(P)

翻倍后。然而，将两边除以 2 我们可以看到 P' 在加倍之前一定也更短，所以 P 不是开始的最短路径，我们有一个矛盾。因此，在边缘权重加倍后，P仍然是最短路径。

有人可以批评这个解决方案吗？正确吗？

Answer 1

是的，最短路径保持不变。对边权重应用线性变换不会更改最短路径，只要不否定边权重即可。