Consider a directed graph
G = (V,E)with non-negative costs on each edge. With
sbeing a starting vertex. Prove that by adding a constant
kto each edge
(s,u) ∈ Esuch as
u ∈ V, the shortest path tree starting from
swill 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.