graph_shortest_path/
lib.rs

1//! # graph-shortest-path
2//!
3//! Shortest-path algorithms built on top of [`graph_core`]'s [`Graph`] trait.
4//!
5//! Every algorithm accepts any type implementing `Graph<Weight = f64>`, so it
6//! works with both [`AdjacencyList`] and [`AdjacencyMatrix`] out of the box.
7//!
8//! ## Algorithms
9//!
10//! | Module            | Algorithm                          | Complexity         |
11//! |-------------------|------------------------------------|--------------------|
12//! | [`mod@dijkstra`]      | Dijkstra (single-source)           | O((V+E) log V)     |
13//! | [`mod@bellman_ford`]  | Bellman-Ford (negative weights)    | O(V·E)             |
14//! | [`mod@floyd_warshall`]| Floyd-Warshall (all-pairs)         | O(V³)              |
15//! | [`mod@astar`]         | A* (goal-directed, heuristic)      | O(E log V)         |
16//!
17//! [`Graph`]: graph_core::Graph
18//! [`AdjacencyList`]: graph_core::AdjacencyList
19//! [`AdjacencyMatrix`]: graph_core::AdjacencyMatrix
20
21/// A* goal-directed shortest path with a caller-supplied heuristic.
22pub mod astar;
23/// Bellman-Ford single-source shortest path; handles negative weights.
24pub mod bellman_ford;
25/// Dijkstra's single-source shortest path for non-negative weights.
26pub mod dijkstra;
27/// Floyd-Warshall all-pairs shortest path.
28pub mod floyd_warshall;
29
30pub use astar::astar;
31pub use bellman_ford::{bellman_ford, BellmanFordResult};
32pub use dijkstra::{dijkstra, DijkstraResult};
33pub use floyd_warshall::floyd_warshall;
graph_shortest_path/lib.rs

graph_shortest_path/
lib.rs
