pathfinding
This crate implements several pathfinding, flow, and graph algorithms in Rust
- A*: find the shortest path in a weighted graph using an heuristic to guide the process.
- breadth-first search (BFS): explore nearest neighbours first, then widen the search.
- depth-first search (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 directed graph.
- 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.
- Kuhn-Munkres: find the maximum (or minimum) matching in a weighted bipartite graph.
Those algorithms are generic over their arguments.
Using this crate
In your Cargo.toml
, put:
[dependencies]
pathfinding = "0.4"
You can then pull your preferred algorithm (BFS in this example) using:
extern crate pathfinding;
use bfs;
Example
We will search the shortest path on a chess board to go from (1, 1) to (4, 6) doing only knight moves.
use bfs;
;
static GOAL: Pos = Pos;
let result = bfs;
assert_eq!;
License
This code is released under a dual Apache 2.0 / MIT free software license.