advanced_algorithms/graph/
dijkstra.rs

1//! Dijkstra's Algorithm
2//!
3//! Finds the shortest path from a source node to all other nodes in a weighted graph
4//! with non-negative edge weights. One of the most famous algorithms in computer science.
5//!
6//! Time complexity: O((V + E) log V) with binary heap
7//!
8//! # Examples
9//!
10//! ```
11//! use advanced_algorithms::graph::{Graph, dijkstra};
12//!
13//! let mut graph = Graph::new(5);
14//! graph.add_edge(0, 1, 4.0);
15//! graph.add_edge(0, 2, 1.0);
16//! graph.add_edge(2, 1, 2.0);
17//! graph.add_edge(1, 3, 1.0);
18//! graph.add_edge(2, 3, 5.0);
19//!
20//! let result = dijkstra::shortest_path(&graph, 0);
21//! assert_eq!(result.distance[3], 4.0); // 0->2->1->3
22//! ```
23
24use crate::graph::Graph;
25use std::collections::BinaryHeap;
26use std::cmp::Ordering;
27
28/// Node in the priority queue
29#[derive(Debug, Clone)]
30struct State {
31    node: usize,
32    distance: f64,
33}
34
35impl Eq for State {}
36
37impl PartialEq for State {
38    fn eq(&self, other: &Self) -> bool {
39        self.distance == other.distance && self.node == other.node
40    }
41}
42
43impl Ord for State {
44    fn cmp(&self, other: &Self) -> Ordering {
45        // Reverse ordering for min-heap
46        other.distance.partial_cmp(&self.distance)
47            .unwrap_or(Ordering::Equal)
48            .then_with(|| self.node.cmp(&other.node))
49    }
50}
51
52impl PartialOrd for State {
53    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
54        Some(self.cmp(other))
55    }
56}
57
58/// Result of Dijkstra's algorithm
59#[derive(Debug, Clone)]
60pub struct ShortestPathResult {
61    /// Distance from source to each node
62    pub distance: Vec<f64>,
63    /// Previous node in shortest path
64    pub previous: Vec<Option<usize>>,
65    /// Source node
66    pub source: usize,
67}
68
69impl ShortestPathResult {
70    /// Reconstructs the path from source to target
71    pub fn path_to(&self, target: usize) -> Option<Vec<usize>> {
72        if self.distance[target].is_infinite() {
73            return None;
74        }
75        
76        let mut path = Vec::new();
77        let mut current = target;
78        
79        while current != self.source {
80            path.push(current);
81            current = self.previous[current]?;
82        }
83        
84        path.push(self.source);
85        path.reverse();
86        
87        Some(path)
88    }
89}
90
91/// Computes shortest paths from source to all nodes using Dijkstra's algorithm
92///
93/// # Arguments
94///
95/// * `graph` - The input graph
96/// * `source` - Starting node
97///
98/// # Returns
99///
100/// ShortestPathResult containing distances and predecessors
101///
102/// # Panics
103///
104/// Panics if the graph contains negative edge weights
105pub fn shortest_path(graph: &Graph, source: usize) -> ShortestPathResult {
106    let n = graph.n_nodes;
107    
108    let mut distance = vec![f64::INFINITY; n];
109    let mut previous = vec![None; n];
110    let mut heap = BinaryHeap::new();
111    
112    distance[source] = 0.0;
113    heap.push(State {
114        node: source,
115        distance: 0.0,
116    });
117    
118    while let Some(State { node, distance: dist }) = heap.pop() {
119        // Skip if we've already found a better path
120        if dist > distance[node] {
121            continue;
122        }
123        
124        // Explore neighbors
125        for &(neighbor, weight) in graph.neighbors(node) {
126            assert!(weight >= 0.0, "Dijkstra's algorithm requires non-negative weights");
127            
128            let new_distance = dist + weight;
129            
130            if new_distance < distance[neighbor] {
131                distance[neighbor] = new_distance;
132                previous[neighbor] = Some(node);
133                
134                heap.push(State {
135                    node: neighbor,
136                    distance: new_distance,
137                });
138            }
139        }
140    }
141    
142    ShortestPathResult {
143        distance,
144        previous,
145        source,
146    }
147}
148
149/// Finds shortest path from source to a specific target node
150///
151/// Returns early once target is reached for efficiency
152pub fn shortest_path_to_target(
153    graph: &Graph,
154    source: usize,
155    target: usize,
156) -> Option<(f64, Vec<usize>)> {
157    let n = graph.n_nodes;
158    
159    let mut distance = vec![f64::INFINITY; n];
160    let mut previous = vec![None; n];
161    let mut heap = BinaryHeap::new();
162    
163    distance[source] = 0.0;
164    heap.push(State {
165        node: source,
166        distance: 0.0,
167    });
168    
169    while let Some(State { node, distance: dist }) = heap.pop() {
170        // Found target
171        if node == target {
172            let result = ShortestPathResult {
173                distance,
174                previous,
175                source,
176            };
177            
178            return Some((dist, result.path_to(target)?));
179        }
180        
181        if dist > distance[node] {
182            continue;
183        }
184        
185        for &(neighbor, weight) in graph.neighbors(node) {
186            let new_distance = dist + weight;
187            
188            if new_distance < distance[neighbor] {
189                distance[neighbor] = new_distance;
190                previous[neighbor] = Some(node);
191                
192                heap.push(State {
193                    node: neighbor,
194                    distance: new_distance,
195                });
196            }
197        }
198    }
199    
200    None
201}
202
203#[cfg(test)]
204mod tests {
205    use super::*;
206    
207    #[test]
208    fn test_simple_path() {
209        let mut graph = Graph::new(4);
210        graph.add_edge(0, 1, 1.0);
211        graph.add_edge(1, 2, 2.0);
212        graph.add_edge(2, 3, 3.0);
213        graph.add_edge(0, 3, 10.0);
214        
215        let result = shortest_path(&graph, 0);
216        
217        assert_eq!(result.distance[3], 6.0);
218        
219        let path = result.path_to(3).unwrap();
220        assert_eq!(path, vec![0, 1, 2, 3]);
221    }
222    
223    #[test]
224    fn test_multiple_paths() {
225        let mut graph = Graph::new(5);
226        graph.add_edge(0, 1, 4.0);
227        graph.add_edge(0, 2, 1.0);
228        graph.add_edge(2, 1, 2.0);
229        graph.add_edge(1, 3, 1.0);
230        graph.add_edge(2, 3, 5.0);
231        graph.add_edge(3, 4, 1.0);
232        
233        let result = shortest_path(&graph, 0);
234        
235        assert_eq!(result.distance[1], 3.0); // via 2
236        assert_eq!(result.distance[3], 4.0); // via 2->1
237        assert_eq!(result.distance[4], 5.0);
238    }
239    
240    #[test]
241    fn test_disconnected() {
242        let mut graph = Graph::new(3);
243        graph.add_edge(0, 1, 1.0);
244        
245        let result = shortest_path(&graph, 0);
246        
247        assert!(result.distance[2].is_infinite());
248        assert!(result.path_to(2).is_none());
249    }
250}
advanced_algorithms/graph/dijkstra.rs

advanced_algorithms/graph/
dijkstra.rs
