Auf sbb.ch kann man ja mit jeglichem Konfort einen Fahrplan berechnen lassen. Nehmen wir ein einfaches Beispiel: Ich möchte am Wochenende von Zürich nach Flims fahren, um dort den Schnee zu genießen.
Man könnte naiverweise zwei Annahmen treffen:
- Das Programm »weiß« (hat es gespeichert), dass man von Zürich über Chur nach Flims fahren muss und sucht nur nach »Zürich – Chur« und »Chur – Flims«, wobei es jeweils direkte Verbindungen gibt.
- Das Programm sucht alle möglichen Verbindungen und wählt dann die kürzesten aus.
Annahme 2. kann schnell verworfen werden: Von Zürich nach Chur kann man auf fast unendlich viele Möglichkeiten gelangen. Das Programm »weiß« ja nicht per se, dass wir nicht nach Altstetten fahren und dort auf einen VBZ-Bus umsteigen wollen. Auch so könnte man nach Flims gelangen.
Die Annahme 1. wird die Basis des Algorithmus‘ sein. Der Algorithmus stützt sich aber weit gehend auf den Dijkstra-Algorithmus. Er funktioniert so:
- Es wird ein Netz erstellt, auf dem alle Wege von Zürich nach Flims eingetragen werden.
- Es wird eine geordnete Liste erstellt, in der immer die Destination am Anfang steht, die in der kürzesten Zeit zu erreichen ist.
- Diese Destination wird jeweils durch die Destinationen ersetzt, die von ihr aus zu erreichen sind.
- Es wird wieder geordnet und ersetzt.
- Am Schluss steht in der Liste nur noch das Ziel (der Weg über alle Destinationen hat zum Ziel geführt), alle anderen Destinationen können gelöscht werden.
- Es muss nun nur noch berechnet werden, über welchen Weg man am wenigsten Zeit gebraucht hat.