Kürzester Weg von A nach C(A->B->C) -> kürzester Weg von A nach B

Question

Hallo.

Ich habe folgende Aufgabe:

Sei D = (V,A) ein gerichteter Graph mit Kantenlängenfunktion l: A→R , wobei jeder Kreis in D eine nicht-negative Länge habe. Sei P=(v₀,a₁,v₁....,v_m-1,a_m,v_m) ein kürzester Weg von v₀ nach v_m. Zeigen sie, dass P' = (v₀,a₁,v₁....,v_m-1,a_m) ein kürzester Weg von v₀ nach v_m-1 ist. 

Gilt diese Aussage auch,wenn man in D Kreise negativer Länge erlaubt?

Ich weiß leider nicht genau, wie ich an die Aufgabe rangehen soll. 

Ich habe bereits überlegt, dass weder in P noch in P' keine Kreise enthalten sein können.  Die Aussage müsste auch bei Graphen mit Kreisen negativer Länge erlaubt stimmen, da hier von kürzesten Wegen gesprochen wird und nicht von kürzesten Kantenlängen.

Dass die Aussage,die bewiesen werden soll richtig ist, ist klar(Bsp: ich fahre mit dem Auto auf der Autobahn(ger. Graph) von A nach C. Auf dem Weg liegt B. Ist der Weg von A nach C der kürzeste,so ist auch der Weg von A nach B der kürzeste(B nach C gilt das selbe).

Könnte mit jemand vielleich bei den Ansätzen helfen?

Comments

Wenn $P'$ nicht der kürzeste Weg von $v_0$ nach $v_{m-1}$ ist, existiert ein Weg $\widetilde{P'}$ von $v_0$ nach $v_{m-1}$, der kürzer als $P'$ ist. Was passiert, wenn du über $\widetilde{P'}$ nach $v_{m-1}$ gehst und dann über $a_m$ nach $v_m$? Was gilt für diesen neuen Weg?

---

Ah alles klar, danke :D

Also kurz geschrieben fehlt dann noch:

$$l (\widetilde {P'})<l(P')$$

Dann müsste auch gelten:

$$l (\widetilde {P'})+l({ a }_{ 1 })<l(P)$$

Das ist ein Widerspruch,da P ja bereits kürzester Weg ist.

P.S.: Ich wusste irgendwie, dass du derjenige bist, der die Antwort gibt.