# Increasing every starting edge by a constant, then the shortest path tree remains the same?

Consider a directed graph G = (V,E) with non-negative costs on each edge. With s being a starting vertex. Prove that by adding a constant k to each edge (s,u) ∈ E such as u ∈ V, the shortest path tree starting from s will remain the same.

In an attempt to solve the above question (with a proof) I thought that if we add the same constant factor to every edge the relative order of path weights is preserved.
However, I am not sure how to state the proof correctly.

I have searched a lot, any help would be greatly appreciated.

• Are you only adding weight to edges going from source $s$ to its neighbors or for every edge in the graph? Your title and question are not the same. – ryan Nov 18 '17 at 18:14

## 1 Answer

I think you can prove it by counter-example.

Assume your SPT (shortest path tree) from the original graph is no longer a valid SPT in the new graph. That means there's a node $f$ s.t. the path $(s, n_1, n_2, ..., f)$ in your SPT is no longer a shortest path, meaning some other path $(s, v_1, v_2, ..., f)$ (whose length wasn't shorter before) now has a shorter length.

Now show that's impossible by calculating how much the lengths of those two paths have increased.