Function dijkstra

pub fn dijkstra<G, F, K, E, S>(
    graph: G,
    start: G::NodeId,
    goal: Option<G::NodeId>,
    edge_cost: F,
    path: Option<&mut DictMap<G::NodeId, Vec<G::NodeId>>>,
) -> Result<S, E>
where
    G: IntoEdges + Visitable + NodeIndexable,
    G::NodeId: Eq + Hash,
    F: FnMut(G::EdgeRef) -> Result<K, E>,
    K: Measure + Copy,
    S: DistanceMap<G::NodeId, K>,

Dijkstra’s shortest path algorithm.

Compute the length of the shortest path from start to every reachable node.

The graph should be Visitable and implement IntoEdges. The function edge_cost should return the cost for a particular edge, which is used to compute path costs. Edge costs must be non-negative.

If goal is not None, then the algorithm terminates once the goal node’s cost is calculated.

If path is not None, then the algorithm will mutate the input DictMap to insert an entry where the index is the dest node index the value is a Vec of node indices of the path starting with start and ending at the index.

Returns a DistanceMap that maps NodeId to path cost.

Example

use rustworkx_core::petgraph::Graph;
use rustworkx_core::petgraph::prelude::*;
use rustworkx_core::dictmap::DictMap;
use rustworkx_core::shortest_path::dijkstra;
use rustworkx_core::Result;

let mut graph : Graph<(),(),Directed>= Graph::new();
let a = graph.add_node(()); // node with no weight
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
let g = graph.add_node(());
let h = graph.add_node(());
// z will be in another connected component
let z = graph.add_node(());

graph.extend_with_edges(&[
    (a, b),
    (b, c),
    (c, d),
    (d, a),
    (e, f),
    (b, e),
    (f, g),
    (g, h),
    (h, e)
]);
// a ----> b ----> e ----> f
// ^       |       ^       |
// |       v       |       v
// d <---- c       h <---- g

let expected_res: DictMap<NodeIndex, usize> = [
     (a, 3),
     (b, 0),
     (c, 1),
     (d, 2),
     (e, 1),
     (f, 2),
     (g, 3),
     (h, 4)
    ].iter().cloned().collect();
let res: Result<DictMap<NodeIndex, usize>> = dijkstra(
    &graph, b, None, |_| Ok(1), None
);
assert_eq!(res.unwrap(), expected_res);
// z is not inside res because there is not path from b to z.