Network Source Node

Question

The following is a question from Ahujas book Network Flows:

Show that if we add a constant to the length of every arc emanating from the source node, the shortest path tree remains the same.

I do not know how to prove this. Any recommendations?

Answer 1

If the constant is $k$, the adjusted objective function is $$\sum_{i,j} (c_{i,j}+k[i=s])x_{i,j}= \sum_{i,j} c_{i,j} x_{i,j}+k\sum_j x_{s,j}= \sum_{i,j} c_{i,j} x_{i,j}+k,$$ which differs from the original objective function by the constant $k$ and hence has the same minimizer.