pathfinding
This crate implements several pathfinding and flow 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.
Those algorithms are generic over their arguments.
Using this crate
In your Cargo.toml
, put:
[dependencies]
pathfinding = "0.1"
Or if you don't need the Edmonds-Karp algorithm you can specify this by removing default features:
[dependencies]
# you will compile ndarray only if you need it
pathfinding = { version = "0.1", default-features = false }
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.