pub fn bellman_ford<G>(
g: G,
source: <G as GraphBase>::NodeId
) -> Result<Paths<<G as GraphBase>::NodeId, <G as Data>::EdgeWeight>, NegativeCycle>where
G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable,
<G as Data>::EdgeWeight: FloatMeasure,Expand description
[Generic] Compute shortest paths from node source to all other.
Using the Bellman–Ford algorithm; negative edge costs are permitted, but the graph must not have a cycle of negative weights (in that case it will return an error).
On success, return one vec with path costs, and another one which points out the predecessor of a node along a shortest path. The vectors are indexed by the graph’s node indices.
Example
use petgraph::Graph;
use petgraph::algo::bellman_ford;
use petgraph::prelude::*;
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, 2.0),
(0, 3, 4.0),
(1, 2, 1.0),
(1, 5, 7.0),
(2, 4, 5.0),
(4, 5, 1.0),
(3, 4, 1.0),
]);
// Graph represented with the weight of each edge
//
// 2 1
// a ----- b ----- c
// | 4 | 7 |
// d f | 5
// | 1 | 1 |
// \------ e ------/
let path = bellman_ford(&g, a);
assert!(path.is_ok());
let path = path.unwrap();
assert_eq!(path.distances, vec![ 0.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
assert_eq!(path.predecessors, vec![None, Some(a),Some(b),Some(a), Some(d), Some(e)]);
// Node f (indice 5) can be reach from a with a path costing 6.
// Predecessor of f is Some(e) which predecessor is Some(d) which predecessor is Some(a).
// Thus the path from a to f is a <-> d <-> e <-> f
let graph_with_neg_cycle = Graph::<(), f32, Undirected>::from_edges(&[
(0, 1, -2.0),
(0, 3, -4.0),
(1, 2, -1.0),
(1, 5, -25.0),
(2, 4, -5.0),
(4, 5, -25.0),
(3, 4, -1.0),
]);
assert!(bellman_ford(&graph_with_neg_cycle, NodeIndex::new(0)).is_err());