0 Daumen
372 Aufrufe

Aufgabe:

Sei G= (V,E) ein Graph. Sei s, t, v ∈ V. Der Knoten v liegt genau dann auf einem kürzesten Weg zwischen s und t, wenn gilt: dist(s,t) =dist(s,v)+dist(v,t).


Problem/Ansatz:

Ich weiß nicht genau wie man die Äquivalenz zeigt. Kann man anhand der Definition zeigen dass dist(s,v)+dist(v,t) der kürzseste Weg von s nach t über v ist und dann mit Widerspruch zeigen dass ">"   "<" gilt und damit gleichheit gelten muss? Oder kann man dass nur über Äquivalenzrichtung zeigen?

Avatar von

Ein anderes Problem?

Stell deine Frage