Kurs:Algorithmen und Datenstrukturen/Vorlesung/Berechnung kürzester Weg
Berechnung kürzester Wege
BearbeitenAuf dieser Seite wird die Berechnung der kürzesten Wege behandelt.
Gegeben ist ein (Di-)Graph mit einer Gewichtsfunktion: . Der Pfad durch G ist eine Liste von aneinanderstoßenden Kanten . Das Gewicht oder die Länge eines Pfades ist die Aufsummierung der einzelnen Kantengewichte. . Die Distanz zweier Punkte d(u,v) ist das Gewicht des kürzesten Pfades von u nach v.
Es existieren verschiedene kürzeste Wege Probleme.
SPSP: Single pari shortest path
- Eingabe: Graph G, Startknoten s, Endknoten t
- Ausgabe: Distanz d(s,t)
SSSP: Single source shortest paths
- Eingabe: Graph G, Startknoten s
- Ausgabe: Distanzen d(s,v) für alle Knoten v
APSP: All-pairs shortest paths
- Eingabe: Graph G
- Ausgabe: Distanzen d(v,w) für alle Knoten v,w
Auf den nächsten Seiten lernen wir zwei Algorithmen zum Berechnen des kürzesten Weges kennen.