petgraph/algo/
spfa.rs

1//! Shortest Path Faster Algorithm.
2use alloc::collections::VecDeque;
3
4use super::{bellman_ford::Paths, BoundedMeasure, NegativeCycle};
5use crate::prelude::*;
6use crate::visit::{IntoEdges, IntoNodeIdentifiers, NodeIndexable};
7use alloc::{vec, vec::Vec};
8
9/// Compute shortest paths from node `source` to all other.
10///
11/// Using the [Shortest Path Faster Algorithm][spfa].
12/// Compute shortest distances from node `source` to all other.
13///
14/// Compute shortest paths lengths in a weighted graph with positive or negative edge weights,
15/// but with no negative cycles.
16///
17/// ## Arguments
18/// * `graph`: weighted graph.
19/// * `source`: the source vertex, for which we calculate the lengths of the shortest paths to all the others.
20/// * `edge_cost`: closure that returns the cost of a particular edge.
21///
22/// ## Returns
23/// * `Err`: if graph contains negative cycle.
24/// * `Ok`: a pair of a vector of shortest distances and a vector
25///   of predecessors of each vertex along the shortest path.
26///
27/// ## Complexity
28/// * Time complexity: **O(|V||E|)**, but it's generally assumed that in the average case it is **O(|E|)**.
29/// * Auxiliary space: **O(|V|)**.
30///
31/// where **|V|** is the number of nodes and **|E|** is the number of edges.
32///
33///
34/// [spfa]: https://www.geeksforgeeks.org/shortest-path-faster-algorithm/
35///
36/// # Example
37///
38/// ```
39/// use petgraph::Graph;
40/// use petgraph::algo::spfa;
41///
42/// let mut g = Graph::new();
43/// let a = g.add_node(()); // node with no weight
44/// let b = g.add_node(());
45/// let c = g.add_node(());
46/// let d = g.add_node(());
47/// let e = g.add_node(());
48/// let f = g.add_node(());
49/// g.extend_with_edges(&[
50///     (0, 1, 3.0),
51///     (0, 3, 2.0),
52///     (1, 2, 1.0),
53///     (1, 5, 7.0),
54///     (2, 4, -4.0),
55///     (3, 4, -1.0),
56///     (4, 5, 1.0),
57/// ]);
58///
59/// // Graph represented with the weight of each edge.
60/// //
61/// //     3       1
62/// // a ----- b ----- c
63/// // | 2     | 7     |
64/// // d       f       | -4
65/// // | -1    | 1     |
66/// // \------ e ------/
67///
68/// let path = spfa(&g, a, |edge| *edge.weight());
69/// assert!(path.is_ok());
70/// let path = path.unwrap();
71/// assert_eq!(path.distances, vec![0.0 ,     3.0,     4.0,    2.0,     0.0,     1.0]);
72/// assert_eq!(path.predecessors, vec![None, Some(a), Some(b), Some(a), Some(c), Some(e)]);
73///
74///
75/// // Negative cycle.
76/// let graph = Graph::<(), f32>::from_edges(&[
77///     (0, 1, 2.0), (1, 2, 2.0), (2, 0, -10.0)]);
78///
79/// assert!(spfa(&graph, 0.into(), |edge| *edge.weight()).is_err());
80/// ```
81pub fn spfa<G, F, K>(
82    graph: G,
83    source: G::NodeId,
84    edge_cost: F,
85) -> Result<Paths<G::NodeId, K>, NegativeCycle>
86where
87    G: IntoEdges + IntoNodeIdentifiers + NodeIndexable,
88    F: FnMut(G::EdgeRef) -> K,
89    K: BoundedMeasure + Copy,
90{
91    let ix = |i| graph.to_index(i);
92
93    let pred = vec![None; graph.node_bound()];
94    let mut dist = vec![K::max(); graph.node_bound()];
95    dist[ix(source)] = K::default();
96
97    // Queue of vertices capable of relaxation of the found shortest distances.
98    let mut queue: VecDeque<G::NodeId> = VecDeque::with_capacity(graph.node_bound());
99    let mut in_queue = vec![false; graph.node_bound()];
100
101    queue.push_back(source);
102    in_queue[ix(source)] = true;
103
104    let (distances, predecessors) = spfa_loop(graph, dist, Some(pred), queue, in_queue, edge_cost)?;
105
106    Ok(Paths {
107        distances,
108        predecessors: predecessors.unwrap_or_default(),
109    })
110}
111
112/// The main cycle of the SPFA algorithm. Calculating the predecessors is optional.
113///
114/// The `queue` must be pre-initialized by at least one `source` node.
115/// The content of `in_queue` must match to `queue`.
116#[allow(clippy::type_complexity)]
117pub(crate) fn spfa_loop<G, F, K>(
118    graph: G,
119    mut distances: Vec<K>,
120    mut predecessors: Option<Vec<Option<G::NodeId>>>,
121    mut queue: VecDeque<G::NodeId>,
122    mut in_queue: Vec<bool>,
123    mut edge_cost: F,
124) -> Result<(Vec<K>, Option<Vec<Option<G::NodeId>>>), NegativeCycle>
125where
126    G: IntoEdges + IntoNodeIdentifiers + NodeIndexable,
127    F: FnMut(G::EdgeRef) -> K,
128    K: BoundedMeasure + Copy,
129{
130    let ix = |i| graph.to_index(i);
131
132    // Keep track of how many times each vertex appeared
133    // in the queue to be able to detect a negative cycle.
134    let mut visits = vec![0; graph.node_bound()];
135
136    while let Some(i) = queue.pop_front() {
137        in_queue[ix(i)] = false;
138
139        // In a graph without a negative cycle, no vertex can improve
140        // the shortest distances by more than |V| times.
141        if visits[ix(i)] >= graph.node_bound() {
142            return Err(NegativeCycle(()));
143        }
144        visits[ix(i)] += 1;
145
146        for edge in graph.edges(i) {
147            let j = edge.target();
148            let w = edge_cost(edge);
149
150            let (dist, overflow) = distances[ix(i)].overflowing_add(w);
151
152            if !overflow && dist < distances[ix(j)] {
153                distances[ix(j)] = dist;
154                if let Some(p) = predecessors.as_mut() {
155                    p[ix(j)] = Some(i)
156                }
157
158                if !in_queue[ix(j)] {
159                    in_queue[ix(j)] = true;
160                    queue.push_back(j);
161                }
162            }
163        }
164    }
165
166    Ok((distances, predecessors))
167}
petgraph/algo/spfa.rs

petgraph/algo/
spfa.rs
