1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – ryan Nov 18 '17 at 18:14
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.