Fast Paths
The most famous algorithms used to calculate shortest paths are probably Dijkstra's algorithm and A*. However, shortest path calculation can be done much faster by preprocessing the graph.
Fast Paths uses Contraction Hierarchies, one of the best known speed-up techniques for shortest path calculation. It is especially suited to calculate shortest paths in road networks, but can be used for any directed graph with positive, non-zero edge weights.
Installation
In Cargo.toml
[]
= "0.1.0"
Basic usage
// begin with an empty graph
let mut input_graph = new;
// add an edge between nodes with ID 0 and 6, the weight of the edge is 12.
// Note that the node IDs should be consecutive, if your graph has N nodes use 0...N-1 as node IDs,
// otherwise performance will degrade.
input_graph.add_edge;
// ... add many more edges here
// freeze the graph before using it (you cannot add more edges afterwards, unless you call thaw() first)
input_graph.freeze;
// prepare the graph for fast shortest path calculations. note that you have to do this again if you want to change the
// graph topology or any of the edge weights
let fast_graph = prepare;
// calculate the shortest path between nodes with ID 8 and 6
let shortest_path = calc_path;
match shortest_path
Batch-wise shortest path calculation
For batch-wise calculation of shortest paths the method described above is inefficient. You should keep the PathCalculator
object to execute multiple queries instead:
// ... see above
// create a path calculator (note: not thread-safe, use a separate object per thread)
let mut path_calculator = create_calculator;
let shortest_path = path_calculator.calc_path;
Saving the prepared graph to disk
;
let fast_path_graph = load_from_disk;
save_to_disk
Preparing the graph after changes
The graph preparation can be done much faster using a fixed node ordering, which is just a permutation of node ids. This can be done like this:
let fast_graph = prepare;
let node_ordering = fast_graph.get_node_ordering;
let another_fast_graph = prepare_with_order;
For this to work another_input_graph
must have the same number of nodes as input_graph
, otherwise prepare_with_order
will return an error. Also performance will only be acceptable if input_graph
and another_input_graph
are similar to each other, say you only changed a few edge weights.
Benchmarks
FastPaths was run on a single core on a consumer-grade laptop using the road networks provided for the DIMACS implementation challenge graphs. The following graphs were used for the benchmark:
area | number of nodes | number of edges |
---|---|---|
New York | 264.346 | 733.846 |
California&Nevada | 1.890.815 | 4.630.444 |
USA | 23.947.347 | 57.708.624 |
graph | metric | preparation time | average query time (micros) |
---|---|---|---|
NY city | distance | 24 s | 162 |
CAL&NV | distance | 100 s | 430 |
USA | distance | 35 min | 3980 |
NY city | time | 14 s | 77 |
CAL&NV | time | 62 s | 222 |
USA | time | 13 min | 1086 |
The shortest path calculation time was averaged over 100k random routing queries.
Graph limitations
- loop-edges (from node A to node A) will be ignored, because since we are only considering positive non-zero edge-weights they cannot be part of a shortest path
- in case the graph has duplicate edges (multiple edges from node A to node B) only the edge with the lowest weight will be considered
License
Apache 2.0