Path finding library for Rust
This crate implements several pathfinding, flow, and graph algorithms in Rust.
The algorithms are generic over their arguments.
- A*: find the shortest path in a weighted graph using an heuristic to guide the process.
- BFS: explore nearest successors first, then widen the search.
- Brent: find a cycle in an infinite sequence.
- DFS: explore a graph by going as far as possible, then backtrack.
- Dijkstra: find the shortest path in a weighted graph.
- Edmonds Karp: find the maximum flow in a weighted graph.
- Floyd: find a cycle in an infinite sequence.
- Fringe: find the shortest path in a weighted graph using an heuristic to guide the process.
- IDA*: explore longer and longer paths in a weighted graph at the cost of multiple similar examinations.
- IDDFS: explore longer and longer paths in an unweighted graph at the cost of multiple similar examinations.
- strongly connected components: find strongly connected components in a directed graph.
- topological sorting: find an acceptable topological order in a directed graph.
- Yen: find k-shortest paths using Dijkstra.
- connected components: find disjoint connected sets of vertices.
- Kruskal: find a minimum-spanning-tree.
- Kuhn-Munkres (Hungarian algorithm): find the maximum (or minimum) matching in a weighted bipartite graph.
Gridtype representing a rectangular grid in which vertices can be added or removed, with automatic creation of edges between adjacent vertices.
Matrixtype to store data of arbitrary types, with neighbour-aware methods.
Using pathfindingIn order to use pathfinding, you can add it to your
Cargo.toml as a dependency
The package documentation is available online.
pathfinding = "4.8"
Published version (4.8)You can access the crate from and the .
Development versionYou can get the current development version of pathfinding using git:
This will create a
git clone https://github.com/evenfurther/pathfinding.git
pathfinding directory in which you will be able to record your own changes.
You can also browse the pathfinding repository on GitHub.
Contributing to pathfinding
Reporting bugs and asking for featuresIf you find a bug or have an idea for a new feature, you might consider adding a new issue. The more precise you will be in your description, the more useful it will be.
Patches are gladly accepted from their original author. Along with any patches, please state that the patch is your original work and that you license the work to the pathfinding project under a license compatible with the current one (Apache 2.0 license / MIT license).
To propose a patch, you may fork the pathfinding repository on GitHub, and issue a pull request. You may also send patches and pull requests by email.