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.
In Cargo.toml
```toml [dependencies] fast_paths = "0.1.0"
```
```rust // begin with an empty graph let mut input_graph = InputGraph::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. inputgraph.addedge(0, 6, 12); // ... 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 fastgraph = fastpaths::prepare(&input_graph);
// calculate the shortest path between nodes with ID 8 and 6 let shortestpath = fastpaths::calcpath(&fastpath_graph, 8, 6);
match shortestpath { Some(p) => { // the weight of the shortest path let weight = p.getweight();
// all nodes of the shortest path (including source and target)
let nodes = p.get_nodes();
},
None => {
// no path has been found (nodes are not connected in this graph)
}
}
```
For batch-wise calculation of shortest paths the method described above is inefficient. You should keep the PathCalculator object to execute multiple queries instead:
rust
// ... see above
// create a path calculator (note: not thread-safe, use a separate object per thread)
let mut path_calculator = fast_paths::create_calculator(&fast_path_graph);
let shortest_path = path_calculator.calc_path(&fast_path_graph, 8, 6);
rust
fast_paths::save_to_disk(&fast_path_graph, "fast_path_graph.fp");
let fast_path_graph = fast_paths::load_from_disk("fast_path_graph.fp");
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:
```rust let fastgraph = fastpaths::prepare(&inputgraph); let nodeordering = fastgraph.getnode_ordering();
let anotherfastgraph = fastpaths::preparewithorder(&anotherinputgraph, &nodeordering); ```
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.
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.
Apache 2.0