petgraph 中的哪种算法会找到从 A 到 B 的最短路径?
Which algorithm from petgraph will find the shortest path from A to B?
我有一个方向图,想找到从节点 A 到节点 B 的最短路径。我在 crates.io and found petgraph which looks like the most popular crate. It implements a number of algorithms 上进行了搜索,但其中 none 解决了我的任务。我错过了什么吗?
例如,Dijkstra's algorithm returns path costs, but which path has the minimum cost? The Bellman-Ford algorithm returns 路径成本
和节点,但没有路径。
这是我发现的从图中打印路径的最简单方法:
extern crate petgraph;
use petgraph::prelude::*;
use petgraph::algo::dijkstra;
fn main() {
let mut graph = Graph::<&str, i32>::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 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
.
我相信如果我自己实现 dijkstra
(基于我的实现 dijkstra.rs),并取消注释 predecessor
和 return [=13] =],最终的变体会更快,因为答案类似于 predecessor[predecessor[d]]
.
作为(图书馆的主要作者,不少于),你可以使用A*(astar
)算法:
use petgraph::{algo, prelude::*}; // 0.5.1
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)]
我有一个方向图,想找到从节点 A 到节点 B 的最短路径。我在 crates.io and found petgraph which looks like the most popular crate. It implements a number of algorithms 上进行了搜索,但其中 none 解决了我的任务。我错过了什么吗?
例如,Dijkstra's algorithm returns path costs, but which path has the minimum cost? The Bellman-Ford algorithm returns 路径成本 和节点,但没有路径。
这是我发现的从图中打印路径的最简单方法:
extern crate petgraph;
use petgraph::prelude::*;
use petgraph::algo::dijkstra;
fn main() {
let mut graph = Graph::<&str, i32>::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 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
.
我相信如果我自己实现 dijkstra
(基于我的实现 dijkstra.rs),并取消注释 predecessor
和 return [=13] =],最终的变体会更快,因为答案类似于 predecessor[predecessor[d]]
.
作为astar
)算法:
use petgraph::{algo, prelude::*}; // 0.5.1
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)]