dijkstra.rs

use std::collections::HashMap;
use std::hash::{Hash, Hasher};

struct Node
{
    value : i32,
    connections : Vec<Edge>
}

impl Hash for Node
{
    fn hash<H: Hasher>(&self, state: &mut H)
    {
        self.value.hash(state);
    }
}

impl PartialEq for Node
{
    fn eq(&self, other: &Node) -> bool
    {
        self.value == other.value
    }
}
impl Eq for Node {}

struct Edge
{
    weight : i32,
    neighbour_id : i32,
}

fn find_minimum_node(distances: &HashMap<i32, u32>, nodes: &HashMap<i32, &Node>) -> i32
{
    let mut min_node_id = -1;
    let mut min_distance = u32::max_value();

    for node in nodes.values()
    {
        let distance = distances[&node.value];
        if distance < min_distance
        {
            min_node_id = node.value;
            min_distance = distance;
        }
    }
    return min_node_id;
}

fn dijkstra_minimum_path(nodes: &[Node], start : i32, end: i32) -> u32
{
    
    let node_set_const : HashMap<i32, &Node> = 
        nodes.iter()
        .map(|node| (node.value, node)).collect();
        
    let mut node_set = HashMap::new();
    let mut distances = HashMap::new();

    for node in nodes
    {
        node_set.insert(node.value, node);
        distances.insert(node.value, u32::max_value());
    }

    distances.insert(start, 0);

    while !node_set.is_empty()
    {
        let minimum_node_id = find_minimum_node(&distances, &node_set);
        let minimum_node = node_set[&minimum_node_id];
        node_set.remove(&minimum_node_id);

        for edge in &minimum_node.connections
        {
            let alternative_distance = distances[&minimum_node.value] + edge.weight as u32;
            let neighbouring_distance = distances[&node_set_const[&edge.neighbour_id].value];

            if alternative_distance < neighbouring_distance
            {
                distances.insert(node_set_const[&edge.neighbour_id].value, alternative_distance);
            }
        }
    }
    return distances[&end];
}

fn main() {
    let mut nodes = [
        Node{value: 0, connections: Vec::new()},
        Node{value: 1, connections: Vec::new()},
        Node{value: 2, connections: Vec::new()},
        Node{value: 3, connections: Vec::new()},
        Node{value: 4, connections: Vec::new()},
        Node{value: 5, connections: Vec::new()},
    ];

    nodes[0].connections.push(Edge{weight: 7, neighbour_id: 1});
    nodes[0].connections.push(Edge{weight: 9, neighbour_id: 2});
    nodes[0].connections.push(Edge{weight: 14, neighbour_id: 5});

    nodes[1].connections.push(Edge{weight: 7, neighbour_id: 0});
    nodes[1].connections.push(Edge{weight: 10, neighbour_id: 2});
    nodes[1].connections.push(Edge{weight: 15, neighbour_id: 3});

    nodes[2].connections.push(Edge{weight: 9, neighbour_id: 0});
    nodes[2].connections.push(Edge{weight: 10, neighbour_id: 1});
    nodes[2].connections.push(Edge{weight: 11, neighbour_id: 3});
    nodes[2].connections.push(Edge{weight: 2, neighbour_id: 5});

    nodes[3].connections.push(Edge{weight: 15, neighbour_id: 1});
    nodes[3].connections.push(Edge{weight: 11, neighbour_id: 2});
    nodes[3].connections.push(Edge{weight: 6, neighbour_id: 4});

    nodes[4].connections.push(Edge{weight: 6, neighbour_id: 3});
    nodes[4].connections.push(Edge{weight: 9, neighbour_id: 5});

    nodes[5].connections.push(Edge{weight: 14, neighbour_id: 0});
    nodes[5].connections.push(Edge{weight: 2, neighbour_id: 2});
    nodes[5].connections.push(Edge{weight: 9, neighbour_id: 4});

    println!("{}", dijkstra_minimum_path(&nodes, 0, 4));
}