Function petgraph::algo::k_shortest_path [−][src]
pub fn k_shortest_path<G, F, K>(
graph: G,
start: G::NodeId,
goal: Option<G::NodeId>,
k: usize,
edge_cost: F
) -> IndexMap<G::NodeId, K> where
G: IntoEdges + Visitable + NodeCount + NodeIndexable,
G::NodeId: Eq + Hash + Ord,
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; use indexmap::IndexMap; 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: IndexMap<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.