Węzeł źródłowy sieci

Question

Oto pytanie z książki Ahujas Przepływy sieciowe:

Pokaż, że jeśli dodamy stałą do długości każdego łuku wychodzącego z węzła źródłowego, drzewo najkrótszej ścieżki pozostaje takie samo.

Nie wiem, jak to udowodnić. Jakieś zalecenia?

Answer 1

Jeśli stała to $k$, skorygowana funkcja celu to $$\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,$$ która różni się od pierwotnej funkcji celu stałą $k$ i dlatego ma ten sam minimizer.