Function bellman_ford

pub fn bellman_ford<T: Eq + Hash + Clone + Ord>(
    graph: &Graph<T>,
    start: Rc<TreeNode<T>>,
) -> Result<HashMap<Rc<TreeNode<T>>, i32>, String>

Performs the Bellman-Ford algorithm to find the shortest paths from the start node to all other nodes in the graph, even when there are negative edge weights.

This function computes the shortest distance from the start node to every other node and checks for negative weight cycles.

Examples

use std::collections::HashMap;
use std::rc::Rc;
use dsa::data_structures::graph::Graph;
use dsa::algorithms::graph_traversal::bellman_ford;
use dsa::data_structures::tree::TreeNode;

let mut graph = Graph::new();
let node1 = Rc::new(TreeNode::new(1));
let node2 = Rc::new(TreeNode::new(2));
let node3 = Rc::new(TreeNode::new(3));

graph.add_edge(Rc::clone(&node1), Rc::clone(&node2), Some(5));
graph.add_edge(Rc::clone(&node2), Rc::clone(&node3), Some(10));

let result = bellman_ford(&graph, Rc::clone(&node1));

let expected = {
    let mut map = HashMap::new();
    map.insert(Rc::clone(&node1), 0);
    map.insert(Rc::clone(&node2), 5);
    map.insert(Rc::clone(&node3), 15);
    Ok(map)
};

assert_eq!(result, expected);

Parameters

• graph: A reference to the graph on which Bellman-Ford algorithm is to be run.
• start: The node from which the shortest paths are calculated.

Returns

A Result containing a map of nodes to their shortest distances, or an error if a negative weight cycle is detected.