Function petgraph::algo::k_shortest_path::k_shortest_path

pub fn k_shortest_path<G, F, K>(
    graph: G,
    start: G::NodeId,
    goal: Option<G::NodeId>,
    k: usize,
    edge_cost: F
) -> HashMap<G::NodeId, K>
where
    G: IntoEdges + Visitable + NodeCount + NodeIndexable,
    G::NodeId: Eq + Hash,
    F: FnMut(G::EdgeRef) -> K,
    K: Measure + Copy,

[Generic] k’th shortest path algorithm.

Compute the length of the k’th 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.

Computes in *O(k * (|E| + |V|log(|V|))) time (average).

Returns a HashMap that maps NodeId to path cost.

Example

use petgraph::Graph;
use petgraph::algo::k_shortest_path;
use petgraph::prelude::*;
use std::collections::HashMap;

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: HashMap<NodeIndex, usize> = [
     (a, 7),
     (b, 4),
     (c, 5),
     (d, 6),
     (e, 5),
     (f, 6),
     (g, 7),
     (h, 8)
    ].iter().cloned().collect();
let res = k_shortest_path(&graph,b,None,2, |_| 1);
assert_eq!(res, expected_res);
// z is not inside res because there is not path from b to z.