Geht das schlauer?
Geht das schlauer?
Schau dir den Suchbaum für den Graphen von A nach E noch einmal an. Viele Äste erreichen denselben Knoten – aber unterschiedlich lang. Wer zum Beispiel C schon nach 2 km erreicht, braucht den Ast, der C erst nach 5 km erreicht, nicht weiter zu verfolgen: Alles, was danach kommt, wird auf diesem Ast nur länger.
Zeige auf die markierten Stellen im Text – im Suchbaum wird der Ast hervorgehoben.
Aufgabe 2: Von welchem Knoten kennst du den kürzesten Abstand von A schon ganz sicher, wenn du nur die Kanten betrachtest, die direkt von A ausgehen?
Aufgabe 3: Begründe deine Antwort aus Aufgabe 2.
Das Ausbreitungsmodell
Stell dir vor, in Saarlouis (S) läuft Wasser aus und fließt mit gleichbleibender Geschwindigkeit durch alle Straßen in alle Richtungen – eine Minute Fahrzeit entspricht einer Zeiteinheit. Jeder Ort wird genau dann zum ersten Mal erreicht, wenn seit dem Start so viel Zeit vergangen ist wie der schnellste Weg dorthin dauert.
S = Saarlouis, D = Dillingen, L = Lebach, W = Schwalbach, V = Völklingen, P = Püttlingen, R = Riegelsberg, H = Heusweiler, B = Saarbrücken
Werkzeug: Wasser breitet sich aus
Starte die Animation und beobachte, in welcher Reihenfolge die Orte erreicht werden.
- Zeit
- 0
- Erreicht in dieser Reihenfolge
- –
Merke
Die Orte werden in der Reihenfolge ihres kürzesten Abstands vom Start erreicht. Wenn das Wasser einen Ort erreicht, ist dessen kürzester Abstand endgültig – später kann kein kürzerer Weg mehr auftauchen. Genau diese Idee nutzt der Algorithmus im nächsten Kapitel: Er legt die Knoten einen nach dem anderen fest, immer den, den „das Wasser“ als Nächstes erreichen würde.