Relaxation

Sei ein Graph und eine Gewichtung. Beim Relaxieren einer Kante wird geprüft, ob der gerade herausgefundene Pfad zu diesem Knoten kürzer ist als der bisher bekannte. Falls ja, wird die Kante über den neuen besseren Pfad verbunden.

Mit Pseudocode:

if (delta[s][v] > delta[s][u] + weight(u, v)) {
    delta[s][v] = delta[s][u] + weight(u, v);
}

Beispiel

graph LR
	A---|2|B
	A---|4|C
	B---|1|C

• Wir schauen uns alle Knoten von A aus an.
• Wir finden B, zu dem der Pfad 2 kostet, und C, zu dem der Weg 4 kostet. Diese Werte speichern wir, am Besten in den Knoten.
• Wir schauen weiter von B aus: Es gibt einen Weg mit Kosten 1 nach C. Hier wird relaxiert:
  • Bisher war uns nur bekannt, den Weg mit Kosten 4 nach C zu nehmen.
  • Über den Weg mit B sind die Kosten 2+1=3, was kleiner ist als der bisherige Weg.
  • Deswegen wird er “ausgetauscht”.

Siehe auch

• Kürzester Weg