petgraph/algo/
spfa.rs

Help
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 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/// [spfa]: https://www.geeksforgeeks.org/shortest-path-faster-algorithm/
26///
27/// # Example
28///
29/// ```
30/// use petgraph::Graph;
31/// use petgraph::algo::spfa;
32///
33/// let mut g = Graph::new();
34/// let a = g.add_node(()); // node with no weight
35/// let b = g.add_node(());
36/// let c = g.add_node(());
37/// let d = g.add_node(());
38/// let e = g.add_node(());
39/// let f = g.add_node(());
40/// g.extend_with_edges(&[
41///     (0, 1, 3.0),
42///     (0, 3, 2.0),
43///     (1, 2, 1.0),
44///     (1, 5, 7.0),
45///     (2, 4, -4.0),
46///     (3, 4, -1.0),
47///     (4, 5, 1.0),
48/// ]);
49///
50/// // Graph represented with the weight of each edge.
51/// //
52/// //     3       1
53/// // a ----- b ----- c
54/// // | 2     | 7     |
55/// // d       f       | -4
56/// // | -1    | 1     |
57/// // \------ e ------/
58///
59/// let path = spfa(&g, a, |edge| *edge.weight());
60/// assert!(path.is_ok());
61/// let path = path.unwrap();
62/// assert_eq!(path.distances, vec![0.0 ,     3.0,     4.0,    2.0,     0.0,     1.0]);
63/// assert_eq!(path.predecessors, vec![None, Some(a), Some(b), Some(a), Some(c), Some(e)]);
64///
65///
66/// // Negative cycle.
67/// let graph = Graph::<(), f32>::from_edges(&[
68///     (0, 1, 2.0), (1, 2, 2.0), (2, 0, -10.0)]);
69///
70/// assert!(spfa(&graph, 0.into(), |edge| *edge.weight()).is_err());
71/// ```
72pub fn spfa<G, F, K>(
73    graph: G,
74    source: G::NodeId,
75    mut edge_cost: F,
76) -> Result<Paths<G::NodeId, K>, NegativeCycle>
77where
78    G: IntoEdges + IntoNodeIdentifiers + NodeIndexable,
79    F: FnMut(G::EdgeRef) -> K,
80    K: BoundedMeasure + Copy,
81{
82    let ix = |i| graph.to_index(i);
83
84    let mut predecessors = vec![None; graph.node_bound()];
85    let mut distances = vec![K::max(); graph.node_bound()];
86    distances[ix(source)] = K::default();
87
88    // Queue of vertices capable of relaxation of the found shortest distances.
89    let mut queue: Vec<G::NodeId> = Vec::with_capacity(graph.node_bound());
90    let mut in_queue = vec![false; graph.node_bound()];
91
92    queue.push(source);
93    in_queue[ix(source)] = true;
94
95    // Keep track of how many times each vertex appeared
96    // in the queue to be able to detect a negative cycle.
97    let mut visits = vec![0; graph.node_bound()];
98
99    while let Some(i) = queue.pop() {
100        in_queue[ix(i)] = false;
101
102        // In a graph without a negative cycle, no vertex can improve
103        // the shortest distances by more than |V| times.
104        if visits[ix(i)] >= graph.node_bound() {
105            return Err(NegativeCycle(()));
106        }
107        visits[ix(i)] += 1;
108
109        for edge in graph.edges(i) {
110            let j = edge.target();
111            let w = edge_cost(edge);
112
113            let (dist, overflow) = distances[ix(i)].overflowing_add(w);
114
115            if !overflow && dist < distances[ix(j)] {
116                distances[ix(j)] = dist;
117                predecessors[ix(j)] = Some(i);
118
119                if !in_queue[ix(j)] {
120                    in_queue[ix(j)] = true;
121                    queue.push(j);
122                }
123            }
124        }
125    }
126
127    Ok(Paths {
128        distances,
129        predecessors,
130    })
131}
petgraph/algo/spfa.rs

petgraph/algo/
spfa.rs
