Graphen | MathePrisma

Definition

Ist (v,v1,v2,...,vk,w) ein Kantenzug von v nach w, so ist dessen Gewicht die Summe der Gewichte der vorkommenden Kanten

g((v,v1,v2,...,vk,w)) = g({v,v1}) + g({v1,v2}) + ... + g({vk,w})

Im U-Bahn-Beispiel ist ein Kantenzug eine Fahrtstrecke; sein Gewicht ist die Dauer der Fahrt (ohne Wartezeiten beim Umsteigen).

Definition

In einem kantengewichteten Graphen ist der gewichtete Abstand zweier Knoten v und w das kleinste Gewicht aller Kantenzüge, die v und w verbinden.

neue Bezeichnung

Für festes v bezeichnen wir den gewichteten Abstand mit dg(w).

Damit kommen wir zum gewichteten Abstandsproblem. Wir betrachten die Aufgabe

Finde den gewichteten Abstand aller Knoten von einem gegebenen Knoten v und die zugehörigen Wege.

Wenn du am Piccadilly Circus (=v) bist, weißt du dann nicht nur, wie lange es nach King's Cross dauert, sondern auch nach Westminster und Paddington und Baker Street und ... .

gewichtete Abstände

erster Ansatz

Unser früheres Abstandsproblem war eines mit Einheitsgewichtung. Im Algorithmus von Moore hatten wir deshalb d immer um eins erhöht, wenn wir einen Knoten durch das Begehen einer Kante neu entdeckten. Bei gewichteten Kanten interessiert dg, man muss deshalb dg um das Gewicht der begangenen Kante erhöhen.

Können wir ansonsten genau so wie beim Algorithmus von Moore vorgehen?

Eingabe: Graph G, Knoten v dieses Graphen
Ausgabe: Gewichte dg(w) von Kantenzügen, die w und v verbinden.

für alle Knoten w
     setze dg(w) = $\infty$
setze dg(v) = 0
füge v in eine (zunächst leere) Queue D ein
solange D nicht leer ist
     entnehme einen Knoten w aus D
     für alle Kanten {w,u}
          falls dg(u) = $\infty$
               setze dg(u) = dg(w)+g({w,u})
               füge u in D ein

na ja!

Dieser Algorithmus macht's nicht lange richtig:

das Problem

Obwohl bereits besucht, kann der rote Knoten von einem weiteren Knoten aus 'wiederentdeckt' werden, wobei der zugehörige Kantenzug ein kleineres Gewicht hat als der bisher gefundene.
Unser Algorithmus ändert aber ein einmal bestimmtes dg(u) nie mehr.

neuer Versuch

Wir müssen also vorsehen, dass dg(u) später noch nach unten korrigiert werden kann.

Eingabe: Graph G, Knoten v dieses Graphen
Ausgabe: Gewichte dg(w) von Kantenzügen, die w und v verbinden

für alle Knoten w
     setze dg(w) = $\infty$
setze dg(v) = 0
füge v in eine (zunächst leere) Queue D ein
solange D nicht leer ist
     entnehme einen Knoten w aus D
     für alle Kanten {w,u}
          falls dg(u) = $\infty$
               füge u in D ein
          falls dg(u) > dg(w) + g({w,u})
               setze dg(u) = dg(w)+g({w,u})

besser, aber nicht gut genug

Dieser Algorithmus bekommt seine Probleme etwas später ...

das nächste Problem

Beim roten Knoten wurde der richtige Wert für dg erst bestimmt, als der Knoten bereits aus D entnommen war. Von diesen Knoten aus müsste man also nochmals suchen, was unser Algorithmus aber nicht tut. Er 'findet' deshalb den roten Kantenzug nicht.

Abhilfe 1

Man fügt die Knoten, für die sich dg ändert, wieder in D ein.

Abhilfe 2

Raffinierter - weil effizienter - ist ein Vorgehen, bei dem man aus D immer den 'richtigen' Knoten entnimmt. (D ist dann keine Queue mehr.)