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

Berechnung kürzester Wege

Auf dieser Seite wird die Berechnung der kürzesten Wege behandelt.

Gegeben ist ein (Di-)Graph $G=(V,E,\gamma )$ mit einer Gewichtsfunktion: $\gamma :E\to \mathbb{N}$. Der Pfad durch G ist eine Liste von aneinanderstoßenden Kanten $P=\{(v_1,v_2),(v_2,v_3),...(v_{n-1},v_n)\}\subseteq E$. Das Gewicht oder die Länge eines Pfades ist die Aufsummierung der einzelnen Kantengewichte. $w(P)=\sum _{i=1}^{n-1}\gamma ((v_i,v_{i+1}))$. 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.