Nodo de origen de red

Question

La siguiente es una pregunta del libro Network Flows de Ahujas:

Muestre que si agregamos una constante a la longitud de cada arco que emana del nodo fuente, el árbol de ruta más corto permanece igual.

No sé cómo demostrarlo. ¿Alguna recomendación?

Answer 1

Si la constante es $k$, la función objetivo ajustada es $$\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,$$ que difiere de la función objetivo original por la constante $k$ y por tanto tiene el mismo minimizador.