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)} .
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|) .