pathfinding: a Rust crate of graph, flow and shortest path algorithms

Generic over the graph, which is the whole design

The pathfinding crate implements several pathfinding, flow and graph algorithms in Rust, and the sentence that matters is that the algorithms are generic over their arguments.

That single property explains the shape of the API. Rather than insisting on one graph type, the algorithms take functions and closures describing your data, and work with whatever node type you have. For a search, you supply a start node, a function that enumerates the successors of a node, and a predicate that says whether a node is the goal. The algorithm never needs to know how your nodes are stored, only how to walk from one to its neighbours.

The alternative would be a library that defines its own Graph trait and requires you to convert your data into it. For a large or unusual graph that conversion is often the expensive part, and it is where a library stops being generic in practice. This crate avoids the problem by pushing the representation out to the caller.

The topic tags give a sense of the coverage: astar, dijkstra, edmonds-karp for maximum flow, kuhn-munkres for assignment, and a general graph tag. The crate description in the manifest is pathfinding, flow, and graph algorithms, and the homepage is a personal page rather than a project site. The author is Samuel Tardieu, and the manifest lists the crate under the categories field as algorithms.

Version 4.16.0 is current, with 4.15.0 from 2026-03-10 and 4.14.0 from 2025-01-25 before it, so the release cadence is a few times a year rather than frequent.

Adding the dependency and pulling one algorithm

The dependency goes into Cargo.toml as a normal entry:

[dependencies]
pathfinding = "4.16.0"

Then you pull the algorithm you want from the prelude, in this case breadth-first search:

use pathfinding::prelude::bfs;

The prelude is the ergonomic surface, and it is worth knowing that the crate also has a graph guide document, GRAPH_GUIDE.md, for when you do want a graph structure rather than raw closures.

The runtime requirements are current for Rust. The manifest sets edition to 2024 and rust-version to 1.88.0, so the minimum supported compiler is 1.88.0, and the crate is built with a 2024 edition toolchain.

The dependency list is short and tells you what the crate itself leans on. num-traits for numeric traits, indexmap for insertion-ordered maps, rustc-hash for fast hashing, integer-sqrt for the square root the A* and assignment algorithms need, thiserror for error types, and deprecate-until for marking API that is on its way out. That last one is a deliberate signal, since a crate that exposes a deprecation helper is telling you it expects to change its API over time.

A worked example, and the graph representation guide

The README example is a knight's tour shortest path search on a chess board, and it shows the closure-based API in full.

use pathfinding::prelude::bfs;

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(i32, i32);

impl Pos {
  fn successors(&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);
let result = bfs(&Pos(1, 1), |p| p.successors(), |p| *p == GOAL);
assert_eq!(result.expect("no path found").len(), 5);

Three things to read carefully. The node type is a plain tuple struct with the derives the algorithm needs, including Ord and PartialOrd, which is what lets the same type work with the ordered algorithms. The successors function returns a Vec, so this example allocates per node, which is fine for a board and wrong for a large graph, and the graph guide is where the more careful representations are shown. And the search returns an Option, so a missing path is a normal value rather than a panic.

The GRAPH_GUIDE.md document covers the alternative path. It has comprehensive examples for representing graphs as adjacency lists, adjacency matrices and edge lists, using A* and Dijkstra with weighted graphs, using BFS and DFS with unweighted graphs, practical examples for spatial shortest paths, converting from other languages including R and Python, and tips and best practices.

The examples directory in the repository mirrors that. There are bidirectional variants for both BFS and Dijkstra, which is the case where searching from both ends halves the explored space, and separate files for the adjacency list and adjacency matrix representations, the graph struct, unweighted BFS, a Kuhn-Munkres complexity example and a sliding puzzle.

Two benchmark suites, one of them counting instructions

The benchmarking setup is unusual enough to be worth describing, because it tells you how the maintainer treats performance claims.

There are two kinds. The wall-time benchmarks use Criterion with CodSpeed compatibility, and they live in the benches directory with names like algos.rs and edmondskarp.rs. They are run with:

cargo bench --bench algos --bench edmondskarp --bench kuhn_munkres --bench separate_components

The deterministic benchmarks use iai-callgrind, which counts CPU instructions, cache hits and misses, and estimated cycles using Valgrind. These are prefixed with iai_ and require the iai feature flag, and Valgrind has to be installed first:

# Install valgrind first (required by iai-callgrind)
sudo apt-get install valgrind  # On Ubuntu/Debian

# Run the benchmarks with the feature flag
cargo bench --features iai --bench iai_algos --bench iai_edmondskarp --bench iai_kuhn_munkres --bench iai_separate_components

The reason for the second suite is stated plainly: the iai-callgrind benchmarks provide consistent results across runs and are not affected by system load, making them ideal for detecting performance regressions. They run automatically in CI for all pull requests, comparing performance against the base branch.

This is a deliberate answer to a common problem. Wall-time benchmarks on a shared CI runner are noisy enough that a regression is hard to distinguish from a busy neighbour, and a crate that is a performance library for other people should not accept a slow patch on a noisy measurement. Counting instructions removes the noise at the cost of not reflecting cache behaviour in production conditions.

The manifest shows the feature is a bare flag, iai = [], with the dev dependencies pulling in criterion 0.8, iai-callgrind 0.16.1, itertools, movingai for the classic benchmark grid problems, noisy_float and the rand family, plus trybuild for compile-fail tests and version_check. The random and floating point test dependencies are a signal that the algorithms are tested against randomised inputs rather than only fixed cases.

The lint policy, and the release process

The crate treats lints as policy rather than as advice, and the manifest is explicit about it. The clippy lints table denies the pedantic group, denies missing_const_for_fn, denies redundant_clone and denies allow_attributes, with module_name_repetitions and too_long_first_doc_paragraph allowed, the latter marked as temporary.

Denying allow_attributes is the unusual one. It removes the escape hatch where an inline allow is used to silence a lint locally, which means the allowed set is exactly what is written in the table. The result is a codebase where the lint configuration is the single source of truth rather than something that gets patched per file. It also means a contributor cannot silence a lint they disagree with in the pull request itself, which is a deliberate barrier.

The release configuration is in the manifest too, under package.metadata.release. Commits and tags are signed, and there are pre-release replacements that rewrite the version string in the README and the placeholder in the CHANGELOG, so the documented dependency snippet always matches the published version. The snippet in the README is the one you copy, and it is rewritten on release rather than maintained by hand.

The contribution requirements are also spelled out. Code must be formatted with the latest rustfmt from the nightly toolchain and pass cargo clippy and pre-commit checks, which run automatically on pull requests. The project asks that you open an issue before implementing a new feature, in case it is already in progress, and it uses the conventional commits style, with examples like feat(matrix): add Matrix::transpose() and fix(tests): remove unused imports, and asks that a pull request closing an issue include Fix #xxx or Close #xxx in the cover letter.

What the crate does not do for you

The first limitation is the algorithm list, and there is no general fallback. The crate ships a fixed set of implementations, and if your problem needs something outside it, you implement it yourself or use another crate. For a library whose entire value is the algorithm catalogue, that is the obvious boundary, but it is worth checking the list before you commit to the dependency.

The second limitation is the cost model, which is entirely yours. The generic design means the crate does not know what a move costs in your domain, so you provide it. For a spatial shortest path over a road network, a heuristic that respects the actual distance function is what makes A* worthwhile, and getting that wrong is a silent performance problem rather than a correctness one. The graph guide's spatial shortest path examples and best practices section are the place to look for that.

The third is data structure choice. The example allocates a Vec of successors per node, and the graph structures in the examples exist because that cost matters. The crate depends on indexmap and rustc-hash, so the data structures it does offer are deliberate, but the choice of representation for your specific graph is still on you.

On maintenance, the repository is not archived, the last push was on 2026-10-16, and the most recent release is v4.16.0 from 2026-09-07. The licence deserves a note: the repository metadata is listed as unknown, while the README and the Cargo manifest both state a dual Apache 2.0 / MIT free software licence, with LICENSE-APACHE and LICENSE-MIT both included in the packaged files.

Editorial conclusion

pathfinding suits a Rust project that needs one of the classic graph algorithms and wants control over the graph representation rather than a fixed one, especially when the graph is large enough that a generic implementation and a good data structure matter. It is a poor fit if you need something the crate does not implement, since there is no general fallback, and a poor fit for a graph type that requires a domain-specific cost model that the caller has to supply. Before adopting, read the Graph Guide for the representation that matches your data, check the algorithm list against what you need, and note that the crate targets Rust edition 2024 with rust-version 1.88.0 as the minimum.

Frequently asked questions

Official sources

1. evenfurther/pathfinding on GitHub
2. Issues
3. README
4. Releases