Function spfa

pub fn spfa<G, F, K>(
    graph: G,
    source: G::NodeId,
    edge_cost: F,
) -> Result<Paths<G::NodeId, K>, NegativeCycle>
where
    G: IntoEdges + IntoNodeIdentifiers + NodeIndexable,
    F: FnMut(G::EdgeRef) -> K,
    K: BoundedMeasure + Copy,

[Generic] Compute shortest paths from node source to all other.

Using the Shortest Path Faster Algorithm. Compute shortest distances from node source to all other.

Compute shortest paths lengths in a weighted graph with positive or negative edge weights, but with no negative cycles.

Arguments

• graph: weighted graph.
• source: the source vertex, for which we calculate the lengths of the shortest paths to all the others.
• edge_cost: closure that returns cost of a particular edge

Returns

• Err: if graph contains negative cycle.
• Ok: a pair of a vector of shortest distances and a vector of predecessors of each vertex along the shortest path.

Example

use petgraph::Graph;
use petgraph::algo::spfa;

let mut g = Graph::new();
let a = g.add_node(()); // node with no weight
let b = g.add_node(());
let c = g.add_node(());
let d = g.add_node(());
let e = g.add_node(());
let f = g.add_node(());
g.extend_with_edges(&[
    (0, 1, 3.0),
    (0, 3, 2.0),
    (1, 2, 1.0),
    (1, 5, 7.0),
    (2, 4, -4.0),
    (3, 4, -1.0),
    (4, 5, 1.0),
]);

// Graph represented with the weight of each edge.
//
//     3       1
// a ----- b ----- c
// | 2     | 7     |
// d       f       | -4
// | -1    | 1     |
// \------ e ------/

let path = spfa(&g, a, |edge| *edge.weight());
assert!(path.is_ok());
let path = path.unwrap();
assert_eq!(path.distances, vec![0.0 ,     3.0,     4.0,    2.0,     0.0,     1.0]);
assert_eq!(path.predecessors, vec![None, Some(a), Some(b), Some(a), Some(c), Some(e)]);


// Negative cycle.
let graph = Graph::<(), f32>::from_edges(&[
    (0, 1, 2.0), (1, 2, 2.0), (2, 0, -10.0)]);

assert!(spfa(&graph, 0.into(), |edge| *edge.weight()).is_err());