Function graphalgs::shortest_path::spfa
source · pub fn spfa<G>(
graph: G,
source: G::NodeId
) -> Result<(Vec<G::EdgeWeight>, Vec<Option<G::NodeId>>), NegativeCycle>where
G: IntoEdges + IntoNodeIdentifiers + NodeIndexable,
G::EdgeWeight: FloatMeasure,
Expand description
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.
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.
Examples
use petgraph::Graph;
use graphalgs::shortest_path::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 ------/
assert_eq!(spfa(&g, a), Ok((vec![0.0 , 3.0, 4.0, 2.0, 0.0, 1.0],
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()).is_err());