네트워크 소스 노드

Question

다음은 Ahujas 책 Network Flows의 질문입니다.

소스 노드에서 나오는 모든 호의 길이에 상수를 추가하면 최단 경로 트리는 동일하게 유지됩니다.

나는 이것을 증명하는 방법을 모른다. 권장 사항이 있습니까?

Answer 1

상수가 $k$, 조정 된 목적 함수는 $$\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,$$ 상수에 의해 원래 목적 함수와 다른 $k$ 따라서 동일한 최소화 기가 있습니다.