Function dijkstra

pub fn dijkstra<T: Eq + Hash + Clone + Ord>(
    graph: &Graph<T>,
    start: Rc<TreeNode<T>>,
) -> HashMap<Rc<TreeNode<T>>, u32>

Performs Dijkstra’s algorithm to find the shortest path from the start node to all other nodes in the graph.

This function computes the shortest distance from the start node to every other node in the graph and returns a map of nodes to their corresponding shortest distances.

Examples

use std::collections::HashMap;
use std::rc::Rc;
use dsa::algorithms::graph_traversal::dijkstra;
use dsa::data_structures::graph::Graph;
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 = dijkstra(&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);
    map
};

assert_eq!(result, expected);

Parameters

• graph: A reference to the graph on which Dijkstra’s algorithm is to be run.
• start: The node from which the shortest paths are calculated.

Returns

A map of nodes to their shortest distances from the start node.