Kurs:Algorithmen und Datenstrukturen/Vorlesung/Berechnung kürzester Weg




Berechnung kürzester Wege

Bearbeiten

Auf 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.