The FasterPaths Rust crate provides highly efficient pathfinding algorithms designed for static graphs (i.e., graphs that do not change over time).
Currently, FasterPaths implements two advanced techniques for enhanced performance:
- Contraction Hierarchies
- Hub Labels
Both techniques necessitate some preprocessing, which aims to be as brief as possible.
Contraction Hierarchies simplify the graph by allowing bidirectional search queries on a contracted version of the graph. This approach significantly reduces the number of vertices visited during the search.
Hub Labels involve calculating a label for each vertex, representing the shortest path tree of a bidirectional search on a contracted graph. The weight of a shortest path is the minimal weight overlap of two labels.
- Vertices must be continuously numbered starting from zero and are represented as
u32. - Edge weights are also
u32and non-negative. - Self-edges are not allowed.
A path is list of vertices where each consecutive pair of vertices is connected by an edge in the graph. Therefore, in the logic of the crate, a shortest path from v to v does not exists.