Shortest path after doubling edge weights

Question

Suppose we have a weighted directed graph G and we've found the shortest path between vertices u and v in G using A* search or any other shortest path algorithm. Now suppose that we double all of the edge weights in G. Does the shortest path change?

My argument is as follows: the shortest path does not change. Call the original path P and suppose that there exists a second, different path P' from u to v such that after doubling the weights of the edges, P' is shorter than P. Then,

    weight(P') < weight(P)

after the doubling. However, dividing both sides by 2 we see that P' must have also been shorter before the doubling, so P was not the shortest path to begin with and we have a contradiction. Thus, P remains the shortest path after doubling the edge weights.

Could someone critique this solution? Is it correct?

Answer 1

Yes, the shortest path remains the same. Applying a linear transformation to the edge weights does not change the shortest path, so long as you do not negate the edge weights.