# pathfinding
[](https://travis-ci.org/samueltardieu/pathfinding)
[](https://ci.appveyor.com/project/samueltardieu/pathfinding)
[](https://crates.io/crates/pathfinding)
[](https://docs.rs/pathfinding)
[](#license)
This crate implements several pathfinding, flow, and graph algorithms in [Rust][Rust]
- [A*][A*]: find the shortest path in a weighted graph using an heuristic to guide the process.
- [breadth-first search (BFS)][BFS]: explore nearest neighbours first, then widen the search.
- [depth-first search (DFS)][DFS]: explore a graph by going as far as possible, then backtrack.
- [Dijkstra][Dijkstra]: find the shortest path in a weighted graph.
- [Edmonds Karp][Edmonds Karp]: find the maximum flow in a directed graph.
- [Fringe][Fringe]: find the shortest path in a weighted graph using an heuristic to guide the process.
- [IDA*][IDA*]: explore longer and longer paths in a weighted graph at the cost of multiple similar examinations.
- [Kuhn-Munkres][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:
``` ini
[dependencies]
pathfinding = "0.4"
```
You can then pull your preferred algorithm (BFS in this example) using:
``` rust
extern crate pathfinding;
use pathfinding::bfs;
```
## Example
We will search the shortest path on a chess board to go from (1, 1) to (4, 6) doing only knight
moves.
``` rust
use pathfinding::bfs;
#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(i32, i32);
impl Pos {
fn neighbours(&self) -> Vec<Pos> {
let &Pos(x, y) = self;
vec![Pos(x+1,y+2), Pos(x+1,y-2), Pos(x-1,y+2), Pos(x-1,y-2),
Pos(x+2,y+1), Pos(x+2,y-1), Pos(x-2,y+1), Pos(x-2,y-1)]
}
}
static GOAL: Pos = Pos(4, 6);