6 Kürzeste Wege Probleme

Gegeben: G = (V,E) ungerichteter Graph

Gesucht: der kürzeste Weg vom Knoten A zum Knoten B

Bedeutet ``kürzester Weg'' der Weg mit minimaler Kantenzahl, so läßt sich dieser kürzeste Weg mit einer Breitensuche mit Wurzel A berechnen. Falls ``kurz'' jedoch bedeutet, daß der Weg mit minimaler Summe der Kantenkosten gesucht wird, so ist ein brauchbarer Algorithmus nicht ohne weiteres zu finden.

Idee: Konstruiere einen Baum mit Wurzel A und füge jeweils den Knoten mit kleinstem Abstand zu A hinzu.

Analog zu Prim bearbeiten wir für einen Knoten x alle seine Nachbarn y und ersetzen ihre Bewertung m(y) durch m(y) : = min {m(y),m(x) + c(x,y)} .

Behauptung:

Alle Knoten im so entstehenden Baum sind mit den korrekten kürzesten Wegekosten zu A notiert. Im Rand und im Rest sind die Knoten mit den kürzesten Wegekosten zu A markiert, wobei die Wege aber nur über Baumknoten laufen.

Beweis: (durch Induktion)

Verankerung: klar!

Schritt: Das Minimum x in Rand und Rest kann endgültig markiert werden, da der kürzeste Weg von A zu x nur über Baumknoten laufen kann. Wichtig hierfür sind allerdings positive Kantenkosten!

Die Laufzeit eines auf dieser Idee basierenden Algorithmus läge also in O(|E| · log |V|) .