更新时间:2022-12-17 10:48:23
As mentioned in the comments (by the library's primary author, no less), you can use the A* (astar
) algorithm:
use petgraph::{algo, prelude::*}; // 0.4.13
fn main() {
let mut graph = Graph::new();
let a = graph.add_node("a");
let b = graph.add_node("b");
let c = graph.add_node("c");
let d = graph.add_node("d");
graph.extend_with_edges(&[(a, b, 1), (b, c, 1), (c, d, 1), (a, b, 1), (b, d, 1)]);
let path = algo::astar(
&graph,
a, // start
|n| n == d, // is_goal
|e| *e.weight(), // edge_cost
|_| 0, // estimate_cost
);
match path {
Some((cost, path)) => {
println!("The total cost was {}: {:?}", cost, path);
}
None => println!("There was no path"),
}
}
The total cost was 2: [NodeIndex(0), NodeIndex(1), NodeIndex(3)]