Network Source Node

Question

Quella che segue è una domanda tratta dal libro Network Flows di Ahujas:

Mostra che se aggiungiamo una costante alla lunghezza di ogni arco emanato dal nodo sorgente, l'albero del percorso più breve rimane lo stesso.

Non so come dimostrarlo. Qualche consiglio?

Answer 1

Se la costante è $k$, la funzione obiettivo regolata è $$\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,$$ che differisce dalla funzione obiettivo originale per la costante $k$ e quindi ha lo stesso minimizer.