# 生锈 – petgraph的哪种算法会找到从A到B的最短路径？

``````extern crate petgraph;
use petgraph::prelude::*;
use petgraph::algo::dijkstra;

fn main() {
let mut graph = Graph::<&str, i32>::new();

graph.extend_with_edges(&[(a, b, 1), (b, c, 1), (c, d, 1), (a, b, 1), (b, d, 1)]);
let paths_cost = dijkstra(&graph, a, Some(d), |e| *e.weight());
println!("dijkstra {:?}", paths_cost);

let mut path = vec![d.index()];
let mut cur_node = d;

while cur_node != a {
let m = graph
.edges_directed(cur_node, Direction::Incoming)
.map(|edge| paths_cost.get(&edge.source()).unwrap())
.min()
.unwrap();
let v = *m as usize;
path.push(v);
cur_node = NodeIndex::new(v);
}

for i in path.iter().rev().map(|v| graph[NodeIndex::new(*v)]) {
println!("path: {}", i);
}
}
``````

Dijkstra算法.

``````extern crate petgraph;

use petgraph::prelude::*;
use petgraph::algo;

fn main() {
let mut graph = Graph::new();

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)]
``````