Shortest path after doubling edge weights

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?

1 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.

I think that might be slightly overstated. Multiplying every edge weight by a positive constant factor will not change the shortest path - that is correct (because multiplication distributes over addition). However, adding 1 to every path edge, which is also a "linear transformation", will penalize those paths with more segments to a greater degree than those with fewer segments, which will often mean there is a different shortest path.

@twalberg Adding 1 to each weight is more properly described as "affine", but I agree that the wording here leaves something to be desired.

@DavidEisenstat Hmmm. Yes, I believe you're right. it's been a few . years . since I was last fully versed in linear algebra concepts, so the vocabulary has slipped a bit. But if the distinction is between linear vs higher-order polynomials, exponentials, transcendentals and such, considering affine transformations under the umbrella of "linear" isn't too far afield.