Assuming the weight of every edge in a directed weighted graph is greater than…

Concept

The shortest path between two vertices is found by comparing the sum of edge weights along every possible path between them; different paths connecting the same pair of vertices can use a different number of edges. So a transformation applied to every edge weight keeps the shortest path unchanged only if it preserves the relative order of every path's total, for any graph.

Application

1. Let W(P) denote the total weight of a path P, i.e. the sum of the weights of its edges.

2. Scaling every edge weight by a positive factor k changes every path's total to k × W(P). Since the SAME factor multiplies every path's total regardless of how many edges it has, if W(P1) was less than W(P2) before scaling, k × W(P1) is still less than k × W(P2) after — the ordering of paths, and hence the shortest path, cannot change.

3. Adding (or subtracting) a constant c to every edge weight instead changes a path's total by c × (the number of edges in that path). Because two paths between u and v can have a different number of edges, this additive shift changes their totals by different amounts, so it can flip which path is shortest.

Cross-check

Take a graph with vertices A, B, C where the direct edge A-C has weight 20, and the path A-B-C has edges of weight 11 and 11 (total 22, using 2 edges) — so A-C directly is the shortest path (20 < 22).

Multiplying every weight by 10 gives totals 200 and 220 — the direct path is still shortest, confirming multiplication preserves the shortest path.

Now instead subtract 10 from every edge weight: the direct edge becomes 10, while A-B-C becomes 1 + 1 = 2 — the shortest path flips to A-B-C, confirming that subtraction (like addition) can change the shortest path.

Result

Only multiplying every edge weight by a positive constant is guaranteed to leave the shortest path between u and v unchanged; adding or subtracting a constant is not.