Which algorithm from petgraph will find the shortest path from A to B?

Question

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?

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);
    }
}

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

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

By your last sentences, you seem to lack an understanding of the Dijkstra and Bellman-Ford algorithms. I would advise you to study them and their outcomes first. — E_net4, Apr 14 '17 at 23:56
@E_net4 I don't understand you, I look at implementation of Dijkstra (https://github.com/bluss/petgraph/blob/master/src/dijkstra.rs), they just comment hashmap that contains resulted path, and not return this path. How knowledge of Dijkstra implementation can help me? — user1244932, Apr 15 '17 at 15:32
Please include what you have tried in your question. If there is a problem with a specific API, do point it out. — E_net4, Apr 15 '17 at 16:41
I suggest you take an extra look at the documentation on `petgraph::algo::dijkstra`, which you linked :) — MartinHaTh, Apr 15 '17 at 17:46
@MartinHaTh I look several times, I can not see answer. I added code to explain why. — user1244932, Apr 15 '17 at 17:51
@user1244932 The key sentences are: (1) "Compute the length of the shortest path from start to every reachable node."; This implies that this implementation doesn't only give you the path from your A to your B, but from your A to *any* B. (2) "Returns a HashMap that maps NodeId to path cost."; This gives you the means of which you can "get out" the actual cost :) — MartinHaTh, Apr 15 '17 at 18:00
@MartinHaTh So can you simplify my code? After call to dijkstra I actually expect to be able to print answer, not `while` loop, search minium and so on. — user1244932, Apr 15 '17 at 18:12

Shepmaster · Accepted Answer · 2021-01-11T14:20:04.857

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

Which algorithm from petgraph will find the shortest path from A to B?

1 Answers1

Linked