GraphHopper is a fast Open Source road routing engine written in Java running on the server as well as on Android. It uses OpenStreetMap as data source and implements road routing via Dijkstra algorithm and variations. In this talk I'll describe the challenges faced while implementing fast and memory efficient graph algorithms and storage solutions.
GraphHopper is a fast Open Source road routing engine written in Java. It uses OpenStreetMap as data source and implements road routing via Dijkstra algorithm and variations. To make shortest-path calculations in under 50ms possible - even for paths of continental length - GraphHopper uses a special "shortcut-technique".
In this talk I'll give you a brief summary of the internal graph representation and how to scale this to gigabytes of memory and still make it running on Android. Including a short overview of Dijkstra, the memory efficient graph traversal API and how to map the real, geographical world with GPS coordinates and roads into a mathematical graph representation with edges and nodes.
Speakers: Peter Karich