Function bellman_ford 

pub fn bellman_ford<G>(
    graph: &G,
    source: NodeId,
) -> Result<BellmanFordResult, GraphError>
where
    G: Graph<Weight = f64>,

Runs the Bellman-Ford algorithm from source.

Unlike Dijkstra, Bellman-Ford handles negative edge weights. It detects negative-weight cycles reachable from source and returns an error if one exists.

Algorithm

Relax all edges V-1 times. On the V-th relaxation pass, if any distance can still be improved a negative-weight cycle exists.

Errors

• GraphError::NodeNotFound if source is not in the graph.
• GraphError::NegativeCycle if a negative-weight cycle is reachable.

Complexity

O(V · E).

Examples

use graph_core::{AdjacencyList, Graph};
use graph_shortest_path::bellman_ford;

let mut g: AdjacencyList<()> = AdjacencyList::directed();
let a = g.add_node(());
let b = g.add_node(());
let c = g.add_node(());
g.add_edge(a, b, 4.0).unwrap();
g.add_edge(a, c, 2.0).unwrap();
g.add_edge(c, b, -1.0).unwrap(); // negative weight, but no negative cycle

let result = bellman_ford(&g, a).unwrap();
assert_eq!(result.distances[&b], 1.0); // a→c→b: 2 + (-1) = 1