petgraph中的哪一种算法会找到从A到B的最短路径? [英] Which algorithm from petgraph will find the shortest path from A to B?

问题描述

我有一个方向图，想找到从节点A到节点B的最短路径.我在 crates.io <上搜索了，发现了宠物图，它看起来像是最受欢迎的板条箱.它实现了多种算法，但是它们都无法解决我的任务.我错过了什么吗?

I have a directional graph and want to find the shortest path from node A to node B. I searched on crates.io and found petgraph which looks like the most popular crate. It implements a number of algorithms, but none of them solve my task. Did I miss something?

例如， Dijkstra的算法返回路径成本，但是哪条路径的成本最低? Bellman-Ford算法返回路径成本 和节点，但没有路径.

For example, Dijkstra's algorithm returns path costs, but which path has the minimum cost? The Bellman-Ford algorithm returns path costs and nodes, but no paths.

这是我发现从图形中打印路径的最简单方法:

This is the simplest way I found to print a path from the graph:

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.

As far as I can see, I need to calculate the path myself based on result of dijkstra.

我相信，如果我自己实现dijkstra(基于 dijkstra.rs )，然后取消对predecessor的注释，并返回predecessor，最终的变体会更快，因为答案将类似于predecessor[predecessor[d]].

I believe that if I implement dijkstra by myself (basing my implementation on dijkstra.rs), and uncomment the lines with predecessor, and return predecessor, the final variant will be faster because the answer will be something like predecessor[predecessor[d]].

推荐答案

为

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

这篇关于petgraph中的哪一种算法会找到从A到B的最短路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！