Nœud de source réseau

Question

Ce qui suit est une question du livre d'Ahujas Network Flows:

Montrez que si nous ajoutons une constante à la longueur de chaque arc émanant du nœud source, l'arbre de chemin le plus court reste le même.

Je ne sais pas comment le prouver. Des recommandations?

Answer 1

Si la constante est $k$, la fonction objectif ajustée est $$\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,$$ qui diffère de la fonction objectif d'origine par la constante $k$ et a donc le même minimiseur.