# Package presentation

cppRouting is an R package which provide functions to calculate distances, shortest paths and isochrones/isodistances on non-negative weighted graphs. For now, cppRouting can implement :

All these functions are written in C++ and use std::priority_queue container from the Standard Template Library.
This package have been made with Rcpp and parallel packages.

# Main functions

cppRouting package provide these functions :

• distance matrix (between all combinations origin-destination nodes),
• distances between origin and destination by pair,
• shortest paths between origin and destination by pair,
• shortest paths between all origin nodes and all destination nodes,
• Isochrones/isodistances with one or multiple breaks.

The choice between all the algorithms is available for get_distance_pair and get_path_pair. In these functions, uni-directional Dijkstra algorithm is stopped when the destination node is reached.
A* and NBA* are relevant if geographic coordinates of all nodes are provided. Note that coordinates should be expressed in a projection system.
To be accurate and efficient, A* and NBA* algorithms should use an admissible heuristic function (here the Euclidean distance), e.g cost and heuristic function must be expressed in the same unit.
In cppRouting, heuristic function h is defined such that : h(xi,yi,xdestination,ydestination)/k, with a constant k; so in the case where coordinates are expressed in meters and cost is expressed in time, k is the maximum speed allowed on the road. By default, constant is 1 and is designed for graphs with cost expressed in the same unit than coordinates (e.g meters).

If coordinates cannot be provided, bi-directional Dijkstra algorithm can offer a good alternative to A* in terms of performance.

# New algorithms cppRouting will provide in the future

• Detours admitting shortest paths : finding the nodes that are reachable under a fixed detour time around the shortest path
• Graph simplification by removing irrelevant nodes in order to compute in a faster way the shortest distance or travel time
• Contraction hierarchies implementation