petgraph/algo/
k_shortest_path.rs

1use alloc::{collections::BinaryHeap, vec, vec::Vec};
2use core::hash::Hash;
3
4use hashbrown::HashMap;
5
6use crate::algo::Measure;
7use crate::scored::MinScored;
8use crate::visit::{EdgeRef, IntoEdges, NodeCount, NodeIndexable, Visitable};
9
10/// \[Generic\] k'th shortest path algorithm.
11///
12/// Compute the length of the k-th shortest path from `start` to every reachable
13/// node. Edge costs must be non-negative.
14///
15/// If `goal` is not `None`, then the algorithm terminates once the `goal` node's
16/// cost is calculated.
17///
18/// # Arguments
19/// * `graph`: an input graph.
20/// * `start`: the *start* node.
21/// * `goal`: optional *goal* node.
22/// * `k`: sequence number of the required shortest paths.
23/// * `edge_cost`: closure that should return the cost for a particular edge, which is used
24///   to compute path costs. Edge costs must be non-negative.
25///
26/// # Returns
27/// * `HashMap`: [`struct@hashbrown::HashMap`] that maps `NodeId` to path cost.
28///
29/// # Complexity
30/// * Time complexity: **O(k|E| log(k|E|))**.
31/// * Auxiliary space: **O(|V| + k|E|)**.
32///
33/// where **|V|** is the number of nodes, **|E|** is the number of edges and **k** is the provided parameter.
34///
35/// # Example
36/// ```rust
37/// use petgraph::Graph;
38/// use petgraph::algo::k_shortest_path;
39/// use petgraph::prelude::*;
40/// use hashbrown::HashMap;
41///
42/// let mut graph : Graph<(),(),Directed>= Graph::new();
43/// let a = graph.add_node(()); // node with no weight
44/// let b = graph.add_node(());
45/// let c = graph.add_node(());
46/// let d = graph.add_node(());
47/// let e = graph.add_node(());
48/// let f = graph.add_node(());
49/// let g = graph.add_node(());
50/// let h = graph.add_node(());
51/// // z will be in another connected component
52/// let z = graph.add_node(());
53///
54/// graph.extend_with_edges(&[
55///     (a, b),
56///     (b, c),
57///     (c, d),
58///     (d, a),
59///     (e, f),
60///     (b, e),
61///     (f, g),
62///     (g, h),
63///     (h, e)
64/// ]);
65/// // a ----> b ----> e ----> f
66/// // ^       |       ^       |
67/// // |       v       |       v
68/// // d <---- c       h <---- g
69///
70/// let expected_res: HashMap<NodeIndex, usize> = [
71///      (a, 7),
72///      (b, 4),
73///      (c, 5),
74///      (d, 6),
75///      (e, 5),
76///      (f, 6),
77///      (g, 7),
78///      (h, 8)
79///     ].iter().cloned().collect();
80/// let res = k_shortest_path(&graph,b,None,2, |_| 1);
81/// assert_eq!(res, expected_res);
82/// // z is not inside res because there is not path from b to z.
83/// ```
84pub fn k_shortest_path<G, F, K>(
85    graph: G,
86    start: G::NodeId,
87    goal: Option<G::NodeId>,
88    k: usize,
89    mut edge_cost: F,
90) -> HashMap<G::NodeId, K>
91where
92    G: IntoEdges + Visitable + NodeCount + NodeIndexable,
93    G::NodeId: Eq + Hash,
94    F: FnMut(G::EdgeRef) -> K,
95    K: Measure + Copy,
96{
97    let mut counter: Vec<usize> = vec![0; graph.node_count()];
98    let mut scores = HashMap::new();
99    let mut visit_next = BinaryHeap::new();
100    let zero_score = K::default();
101
102    visit_next.push(MinScored(zero_score, start));
103
104    while let Some(MinScored(node_score, node)) = visit_next.pop() {
105        counter[graph.to_index(node)] += 1;
106        let current_counter = counter[graph.to_index(node)];
107
108        if current_counter > k {
109            continue;
110        }
111
112        if current_counter == k {
113            scores.insert(node, node_score);
114        }
115
116        //Already reached goal k times
117        if goal.as_ref() == Some(&node) && current_counter == k {
118            break;
119        }
120
121        for edge in graph.edges(node) {
122            visit_next.push(MinScored(node_score + edge_cost(edge), edge.target()));
123        }
124    }
125    scores
126}
petgraph/algo/k_shortest_path.rs

petgraph/algo/
k_shortest_path.rs
