graphrust_algos/

dijkstra.rs

//! Dijkstra's shortest path algorithm implementation.
//!
//! Provides functions for single-source shortest path computation.

use graphrust_core::{EdgeWeight, Graph, NodeId};
use std::collections::{BinaryHeap, HashMap};
use std::cmp::Ordering;

/// State for the priority queue in Dijkstra's algorithm
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
struct State {
    distance: OrderedFloat,
    node: NodeId,
}

/// Wrapper for f64 that implements Ord for use in BinaryHeap
#[derive(Copy, Clone, PartialEq)]
struct OrderedFloat(f64);

impl Eq for OrderedFloat {}

impl PartialOrd for OrderedFloat {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for OrderedFloat {
    fn cmp(&self, other: &Self) -> Ordering {
        // Reverse ordering for min-heap
        other.0.partial_cmp(&self.0).unwrap_or(Ordering::Equal)
    }
}

/// Computes shortest distances from start node to all reachable nodes.
///
/// # Arguments
/// * `graph` - The graph with edge weights
/// * `start_node` - The starting node
///
/// # Returns
/// HashMap mapping each reachable node to its shortest distance from start_node
pub fn dijkstra(graph: &Graph, start_node: NodeId) -> HashMap<NodeId, f64> {
    let mut distances: HashMap<NodeId, f64> = HashMap::new();
    let mut heap = BinaryHeap::new();

    distances.insert(start_node, 0.0);
    heap.push(State {
        distance: OrderedFloat(0.0),
        node: start_node,
    });

    while let Some(State { distance, node }) = heap.pop() {
        let current_distance = distance.0;

        // If we've already found a shorter path to this node, skip it
        if let Some(&known_distance) = distances.get(&node) {
            if current_distance > known_distance {
                continue;
            }
        }

        for &neighbor in graph.neighbors(node) {
            let edge_weight = graph
                .edge_weight(node, neighbor)
                .unwrap_or(EdgeWeight::default());
            let next_distance = current_distance + edge_weight.as_f64();

            let is_new_or_shorter = distances
                .get(&neighbor)
                .map_or(true, |&d| next_distance < d);

            if is_new_or_shorter {
                distances.insert(neighbor, next_distance);
                heap.push(State {
                    distance: OrderedFloat(next_distance),
                    node: neighbor,
                });
            }
        }
    }

    distances
}

/// Computes the shortest path from start to end node.
///
/// # Arguments
/// * `graph` - The graph with edge weights
/// * `start` - The starting node
/// * `end` - The destination node
///
/// # Returns
/// Some(path) if a path exists, None otherwise
pub fn dijkstra_path(graph: &Graph, start: NodeId, end: NodeId) -> Option<Vec<NodeId>> {
    let (distances, predecessors) = dijkstra_with_predecessors(graph, start);

    if !distances.contains_key(&end) {
        return None;
    }

    let mut path = vec![end];
    let mut current = end;

    while current != start {
        current = predecessors.get(&current).copied()?;
        path.push(current);
    }

    path.reverse();
    Some(path)
}

/// Computes shortest distances and predecessor map for path reconstruction.
///
/// # Arguments
/// * `graph` - The graph with edge weights
/// * `start` - The starting node
///
/// # Returns
/// Tuple of (distances HashMap, predecessors HashMap)
pub fn dijkstra_with_predecessors(
    graph: &Graph,
    start: NodeId,
) -> (HashMap<NodeId, f64>, HashMap<NodeId, NodeId>) {
    let mut distances: HashMap<NodeId, f64> = HashMap::new();
    let mut predecessors: HashMap<NodeId, NodeId> = HashMap::new();
    let mut heap = BinaryHeap::new();

    distances.insert(start, 0.0);
    heap.push(State {
        distance: OrderedFloat(0.0),
        node: start,
    });

    while let Some(State { distance, node }) = heap.pop() {
        let current_distance = distance.0;

        if let Some(&known_distance) = distances.get(&node) {
            if current_distance > known_distance {
                continue;
            }
        }

        for &neighbor in graph.neighbors(node) {
            let edge_weight = graph
                .edge_weight(node, neighbor)
                .unwrap_or(EdgeWeight::default());
            let next_distance = current_distance + edge_weight.as_f64();

            let is_new_or_shorter = distances
                .get(&neighbor)
                .map_or(true, |&d| next_distance < d);

            if is_new_or_shorter {
                distances.insert(neighbor, next_distance);
                predecessors.insert(neighbor, node);
                heap.push(State {
                    distance: OrderedFloat(next_distance),
                    node: neighbor,
                });
            }
        }
    }

    (distances, predecessors)
}

#[cfg(test)]
mod tests {
    use super::*;
    use graphrust_core::GraphBuilder;

    fn create_weighted_graph() -> Graph {
        // Create a graph with weighted edges
        GraphBuilder::new(4)
            .directed(true)
            .add_weighted_edge(NodeId(0), NodeId(1), 1.0)
            .add_weighted_edge(NodeId(0), NodeId(2), 4.0)
            .add_weighted_edge(NodeId(1), NodeId(2), 2.0)
            .add_weighted_edge(NodeId(2), NodeId(3), 1.0)
            .build()
    }

    #[test]
    fn test_dijkstra_basic() {
        let graph = create_weighted_graph();
        let distances = dijkstra(&graph, NodeId(0));

        assert_eq!(distances.get(&NodeId(0)), Some(&0.0));
        assert_eq!(distances.get(&NodeId(1)), Some(&1.0));
        assert_eq!(distances.get(&NodeId(2)), Some(&3.0)); // 0->1->2
        assert_eq!(distances.get(&NodeId(3)), Some(&4.0)); // 0->1->2->3
    }

    #[test]
    fn test_dijkstra_path() {
        let graph = create_weighted_graph();
        let path = dijkstra_path(&graph, NodeId(0), NodeId(3));

        assert_eq!(path, Some(vec![NodeId(0), NodeId(1), NodeId(2), NodeId(3)]));
    }

    #[test]
    fn test_dijkstra_no_path() {
        let graph = GraphBuilder::new(4)
            .directed(true)
            .add_weighted_edge(NodeId(0), NodeId(1), 1.0)
            .build();

        let path = dijkstra_path(&graph, NodeId(0), NodeId(3));
        assert_eq!(path, None);
    }

    #[test]
    fn test_dijkstra_with_predecessors() {
        let graph = create_weighted_graph();
        let (distances, predecessors) = dijkstra_with_predecessors(&graph, NodeId(0));

        assert_eq!(distances.get(&NodeId(3)), Some(&4.0));
        assert_eq!(predecessors.get(&NodeId(3)), Some(&NodeId(2)));
        assert_eq!(predecessors.get(&NodeId(2)), Some(&NodeId(1)));
    }
}