Routenplaner: Den kürzesten Weg berechnen mit Dijkstras Algorithmus

Google Maps ist eine hochkomplexe Plattform, doch für die Routenberechnung von A nach B kommt ein uraltes Verfahren zum Einsatz.

Artikel verschenken
In Pocket speichern vorlesen Druckansicht 4 Kommentare lesen
Kürzeste Wege berechnen mit Dijkstras Algorithmus – und viele zusätzliche Daten
Lesezeit: 7 Min.
Von
Inhaltsverzeichnis

"Sie haben Ihr Ziel erreicht." Ein Router wie Google Maps ist längst mehr als ein einfaches Dienstprogramm, das den Nutzer von A nach B bringt. Google Maps ist vielmehr eine komplexe Reiseplattform, die die nächstgelegenen Bäcker inklusive Öffnungszeiten und Kundenbewertungen anzeigt. Und Google ist ein Meister darin, die Crowd dafür einzuspannen, Daten zu diesem Pool beizusteuern. So stammen die Bilder für viele Sehenswürdigkeiten von Freiwilligen – und die Stoßzeiten berechnet Google automatisch aus der Anzahl der Nutzer mit aktivierter Google-Maps-App.

Die Berechnung der Routen ist nur so gut wie die zugrundeliegenden Daten. Google Maps zum Beispiel kartiert längst nicht mehr nur Autostraßen. Es kann Routen auch für Fahrradfahrer, für Fußgänger, für öffentliche Verkehrsmittel und sogar für Flüge berechnen. Dafür bezieht es Kartenmaterial zum Beispiel von Ländern und Gemeinden mit ein, aber auch von Non-Profit-Organisationen oder Firmen.

Außerdem schickt es immer mal wieder Vermessungsautos los, die alte und neue Strecken abfahren, um sie zu kartieren. Dabei erfassen die Fahrerteams nicht nur die reine Strecke, sondern auch den Straßentyp, also etwa, ob es sich um eine Autobahn und Mautstraße handelt. Wie Google Maps und Co. aus den Wegdaten ihre Routen berchnen, zeigt der Kasten. Die aktuelle Herausforderung von Kartenanbietern wie Google Maps ist es, ihre Karten für das autonome Fahren wesentlich genauer zu machen.