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.

Lesezeit: 4 Min.
In Pocket speichern
vorlesen Druckansicht Kommentare lesen 4 Beiträge
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.

Immer mehr Wissen. Das digitale Abo für IT und Technik.

  • Zugriff auf alle Inhalte von heise+
  • exklusive Tests, Ratgeber & Hintergründe: unabhängig, kritisch fundiert
  • c't, iX, Technology Review, Mac & i, Make, c't Fotografie direkt im Browser lesen
  • einmal anmelden – auf allen Geräten lesen - monatlich kündbar
  • erster Monat gratis, danach monatlich 9,95 €
  • Wöchentlicher Newsletter mit persönlichen Leseempfehlungen des Chefredakteurs
GRATIS-Monat beginnen Jetzt GRATIS-Monat beginnen Mehr Informationen zu heise+