Graph representation
This page explains how OSRM converts OSM data to an edge-expanded graph, given that the input data is correct.
In order to use Dijkstra's algorithm, we convert OSM into a graph. We use OSM tags to get speeds, then calculate the duration (in seconds) of each edge, and add some penalties (in seconds) for turns, based on their angle. Once the graph is set up with all the data, finding the route between two points is mostly just a matter of selecting the nodes on the graph, then running Dijkstra's algorithm to find the shortest duration path. Once we have the path, we convert it back to a list of coordinates and turn instructions for spots where a turn was made.
We have lots of optimizations under the hood to make it really fast, but conceptually, it works like any description of Dijkstra you will find.
Data comes from OSM, which has nodes, ways and relations
The geometric representation within OSRM is based on nodes. An OSM node is a 2D point with latitude and longitude, i.e. a geo-coordinate.
An OSM way connects a number of nodes. A way is thus a 2D poly-line, consisting of a number of segments. Several ways can share the same node where they cross.
An OSM relation relates several nodes or ways, or both. It can be used for turn restrictions, routes, and other things. A relation is often not a physical structure, but an abstraction like a bus route for example.
OSRM loads the OSM data, and transforms it into an edge-expanded graph that's better suited for modelling turn costs and turn restrictions. Suppose the following OSM data is loaded:
| | | d |
| a | b | c |
| | | e |
The data consists of two way: abc and dce, meeting at node c.
First, all ways are split into individual segments: ab,bc,cd,ce. For each segment, two graph nodes are created, one for each direction of the segment:
ab, ba
bc, cb
cd, dc
ce, ec
A graph edge is then created for every possible movement taking you from one graph node (direction of a OSM segment) to another. If we allow all turns (including u-turns), in the map above, we get these edges:
dc-cd
dc-cb
dc-ce
ab-ba
ab-bc
ba-ab
bc-cd
bc-cb
bc-ce
cd-dc
cb-ba
cb-bc
ce-ec
ec-cd
ec-cb
ec-ce
Edge have been written in the form "fromGraphNode-toGraphNode". Since we can only move along connected paths, the second graph node always start where the first ends.
The list above includes all possible u-turns, including u-turns in the middle of a way. For example ab-ba represents a u-turn at OSM node b of OSM way abc. OSRM removes such u-turns, and we get:
ab-bc (from ab, continue on bc)
ba-ab (from ba, do a u-turn at a and return on ab)
bc-cd (from bc, turn left onto dc)
bc-ce (from bc, turn right onto ce)
cb-ba (from cb, continue along on ba)
cd-dc (from cd, do a u-turn at d and return on dc)
ce-ec (from ce, do a u turn at e and return on ec)
dc-cb (from dc, turn right onto cd)
dc-ce (from dc, continue on ce)
ec-cd (from ec, continue on cd)
ec-cb (from ec, turn left onto cb)
OSRM will also remove turns that are prohibited by turn restrictions.
Graph nodes represents a specific direction (forward or backward) of an OSM segment. There are two graph nodes for a bidirectional segment, but only one if it's a oneway segment.
Graph edges connect graph nodes, and thus represent transitioning from moving in a specific direction of one OSM segment, to moving in a specific direction of another (or the same) OSM segment. The transition can be either via a turn from one way onto another way, doing a u-turn, or moving from segment to segment along the same way.
Here's an image that shows the basic changes in the graph leading up to the edge-based graph. Some details (bidirectional edges) are ignored for the sake of simplicity:
