Nó Fonte de Rede

Question

A seguir, uma pergunta do livro de Ahujas Network Flows:

Mostre que, se adicionarmos uma constante ao comprimento de cada arco que emana do nó de origem, a árvore do caminho mais curto permanece a mesma.

Não sei como provar isso. Alguma recomendação?

Answer 1

Se a constante for $k$, a função objetivo ajustada é $$\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 difere da função objetivo original pela constante $k$ e, portanto, tem o mesmo minimizador.