Dijkstra router

While building the route, it is essential to find the shortest path from one node on the street graph (which corresponds to a node on the street map) to another.

To find the path, the Dijkstra’s algorithm is used.

Note

The cost function is set to the length of the geometry representing the edge in the street graph, calculated with the haversine formula.

Example

In the following example (see Fig. 15), we want to find a path from node Start to node Goal.

Fig. 15 Street map and street graph

After executing the Dijkstra’s algorithm, we get the shortest route \(r\) as illustrated in Fig. 16.

Fig. 16 Shortest route

Note

As noted in Matching, the routes are in general very short. Between two sampling points, many different routes may get calculated if the sampling point candidates were projected to different street segments.

In the following chapters we learn how the small routes between the street map nodes are used to build the final route.