Nút nguồn mạng

Question

Sau đây là một câu hỏi từ cuốn sách Ahujas Network Flows:

Chứng tỏ rằng nếu chúng ta thêm một hằng số vào độ dài của mọi cung xuất phát từ nút nguồn, thì cây đường đi ngắn nhất vẫn giữ nguyên.

Tôi không biết làm thế nào để chứng minh điều này. Bất kỳ khuyến nghị?

Answer 1

Nếu hằng số là $k$, hàm mục tiêu được điều chỉnh là $$\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,$$ khác với hàm mục tiêu ban đầu bởi hằng số $k$ và do đó có cùng một bộ thu nhỏ.