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

Aus Wikiversity
Zur Navigation springen Zur Suche springen




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.


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg