Node Sumber Jaringan

Question

Berikut ini adalah pertanyaan dari buku Ahujas Network Flows:

Tunjukkan bahwa jika kita menambahkan konstanta ke panjang setiap busur yang berasal dari node sumber, pohon jalur terpendek tetap sama.

Saya tidak tahu bagaimana membuktikannya. Ada rekomendasi?

Answer 1

Jika konstanta adalah $k$, fungsi tujuan yang disesuaikan adalah $$\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,$$ yang berbeda dari fungsi tujuan asli dengan konstanta $k$ dan karenanya memiliki minimizer yang sama.