Sei ein Graph und ein kürzester Weg. Dann ist jeder Teilweg mit auch ein kürzester Weg, und zwar der von nach . Beweis Durch widerspruch