Sei ein Weg und das Gewicht des Weges definiert durch: Dann ist der kürzeste Weg zwischen Zwei Knoten und definiert durch: Misplaced & \min(\{w(p) \ | \ \text{$p$ ist ein Pfad von $u$ nach $v$}\}) & \text{falls es einen Pfad gibt} \\ \infty & \text{sonst} \end{cases}$$ Kürzeste Wege sind nur definiert, wenn es keine [[Negativer Zyklus|negativen Zyklen]] gibt. > [!link] Siehe auch > > - [[Kürzeste-Wege-Problem]] > - [[Optimale Substruktur kürzester Wege]] ## Berechnung kürzester Wege - Häufig sind nicht nur die Werte der kürzesten Wege gefragt, sondern auch die Rückgabe der Wege selbst - Bei `1:n`-[[Kürzeste-Wege-Problem|Problemen]] entsteht ein [[Baum]] - Ähnlich bei der [[Breitensuche]] kann der Baum intern in einem Vorgänger-Feld gespeichert werden > [!link] Siehe auch > > [[Kürzeste-Wege-Problem]]