petgraph/algo/
spfa.rs

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

petgraph/algo/
spfa.rs
