Wie funktioniert eigentlich ein Routenplaner?

Immer mehr Autofahrer verlassen sich heutzutage auf ihr Navigationssystem, das ihnen den besten Weg von ihrem jetzigen Startpunkt zum gewünschten Ziel weisen soll. Doch wie entscheidet der Computer, welches der beste Weg ist?

Bisher hat noch niemand eine Antwort gefunden.
Ich habe eine Theorie! >>

Ein erster Ansatz könnte wie folgt lauten: Probiere alle möglichen Wege aus. Dies würde allerdings viel zu lange dauern; selbst für die Hochleistungsrechner unserer heutigen Zeit wären das zu viele Wege, um sie alle durchzuprobieren.

Den ersten effektiven Algorithmus um einen kürzesten Weg zu berechnen stellte der Mathematiker Dijkstra im Jahre 1959 vor. Der Algorithmus basiert auf der Erkenntnis, dass ein Teilweg eines kürzesten Weges immer auch ein kürzester Weg ist. In anderen Worten: wenn mein kürzester Weg von Berlin nach Bremen über Hannover führt, dann ist auch der Teilweg von Berlin nach Hannover ein kürzester Weg. Wäre dies nicht der Fall, dann könnte ich nämlich diesen Teilweg durch den kürzeren Weg ersetzen und wäre somit auch schneller in Bremen.

Der Ablauf des Algorithmus sieht nun so aus: Man stelle sich vor, dass uns an dem Startknoten viele Läufer zur Verfügung stehen. Diese schicken wir mit der gleichen Geschwindigkeit entlang aller Straßen, die von dem Startknoten ausgehen. Wenn der erste Läufer an einer Kreuzung angekommen ist, stoppen wir kurz. Dort duplizieren wir den Läufer, so dass jetzt jeweils ein Läufer in eine der Straßen, die von der Kreuzung abgehen, weiterlaufen kann. Anschließend, lassen wir alle Läufer weiterlaufen. Sobald wieder ein Läufer an einer neuen Kreuzung angekommen ist, stoppen wir wieder, vervielfältigen ihn, und schicken wieder alle Läufer in die weiteren Straßen.

Kommt jetzt ein Läufer an einer Kreuzung an, die schon erreicht wurde, stoppen wir zwar auch, aber wir nehmen den Läufer aus dem Rennen und lassen alle anderen Läufer weiter laufen. Da wir die Kreuzung schon erreicht hatten, haben wir schon einen kürzeren Weg gefunden, als den, den der Läufer genommen hat. Damit kann dieser Weg nicht mehr zu einem kürzesten Weg führen, wie wir oben beobachtet hatten. Der Algorithmus endet, wenn der erste Läufer im Ziel angekommen ist. Die Strecke, die er hinter sich gebracht hat, ist ein kürzester Weg vom Start zum Ziel.

Der Algorithmus lässt sich auf mehrere Weisen beschleunigen: Lässt man die Läufer gleichzeitig von Start und Ziel aus loslaufen, haben wir einen kürzesten Weg gefunden, sobald sich zwei Läufer aus den beiden Lagern treffen. Bei diesem Vorgehen werden schon eine Menge Läufer und Klon-Schritte gespart. Eine weitere Möglichkeit die Rechenzeit zu verkürzen ist, sich mehr auf Läufer zu konzentrieren, die grob in die richtige Richtung laufen. Ein Läufer, der Richtung Moskau unterwegs ist, wird kaum einen kürzesten Weg von Berlin nach Bremen liefern. Mittlerweile können mit diesen und weiteren Methoden innerhalb von Sekunden optimal Wege von einem Ort zu einem anderen berechnet werden.