Hallo Gucki,
v, w zwei Knoten und \( v \to p_1 \to \dotsm \to p_n \to w \) der kürzeste Pfad zwischen v und w. Sei \( v \to q_1 \to \dotsm \to q_m \to w \) ein anderer Pfad. Mit \( v = p_0 = q_0 \) und \( w = p_{n+1} = q_{m+1} \) ist
$$ \sum_{i=0}^n w(p_i, p_{i+1}) \le \sum_{i=0}^m w(q_i, q_{i+1}) $$
nach der Definition des kürzesten Pfads. Teleskopsumme:
$$ \sum_{i=0}^n w'(p_i, p_{i+1}) = \sum_{i=0}^n \left( w(p_i, p_{i+1}) + f(p_i) - f(p_{i+1}) \right) = f(p_0) - f(p_{n+1}) + \sum_{i=0}^n w(p_i, p_{i+1}) $$
Analog:
$$ \sum_{i=0}^m w'(q_i, q_{i+1}) = f(q_0) - f(q_{m+1}) + \sum_{i=0}^m w(q_i, q_{i+1}) $$
Da \( f(p_0) = f(v) = f(q_0) \) und \( f(p_{n+1}) = f(w) = f(q_{m+1}) \) folgt
$$ \sum_{i=0}^n w'(p_i, p_{i+1}) \le \sum_{i=0}^m w'(q_i, q_{i+1}) $$
Somit bleibt der kürzeste Pfad in G auch der kürzeste Pfad in G'.
