petgraph/algo/dijkstra.rs
1use alloc::collections::BinaryHeap;
2use core::hash::Hash;
3use hashbrown::hash_map::{
4 Entry::{Occupied, Vacant},
5 HashMap,
6};
7
8use crate::algo::Measure;
9use crate::scored::MinScored;
10use crate::visit::{EdgeRef, IntoEdges, IntoEdgesDirected, VisitMap, Visitable};
11use crate::Direction;
12
13/// Dijkstra's shortest path algorithm.
14///
15/// Compute the length of the shortest path from `start` to every reachable
16/// node.
17///
18/// The function `edge_cost` should return the cost for a particular edge, which is used
19/// to compute path costs. Edge costs must be non-negative.
20///
21/// If `goal` is not `None`, then the algorithm terminates once the `goal` node's
22/// cost is calculated.
23///
24/// # Arguments
25/// * `graph`: weighted graph.
26/// * `start`: the start node.
27/// * `goal`: optional *goal* node.
28/// * `edge_cost`: closure that returns cost of a particular edge.
29///
30/// # Returns
31/// * `HashMap`: [`struct@hashbrown::HashMap`] that maps `NodeId` to path cost.
32///
33/// # Complexity
34/// * Time complexity: **O((|V|+|E|)log(|V|))**.
35/// * Auxiliary space: **O(|V|+|E|)**.
36///
37/// where **|V|** is the number of nodes and **|E|** is the number of edges.
38///
39/// # Example
40/// ```rust
41/// use petgraph::Graph;
42/// use petgraph::algo::dijkstra;
43/// use petgraph::prelude::*;
44/// use hashbrown::HashMap;
45///
46/// let mut graph: Graph<(), (), Directed> = Graph::new();
47/// let a = graph.add_node(()); // node with no weight
48/// let b = graph.add_node(());
49/// let c = graph.add_node(());
50/// let d = graph.add_node(());
51/// let e = graph.add_node(());
52/// let f = graph.add_node(());
53/// let g = graph.add_node(());
54/// let h = graph.add_node(());
55/// // z will be in another connected component
56/// let z = graph.add_node(());
57///
58/// graph.extend_with_edges(&[
59/// (a, b),
60/// (b, c),
61/// (c, d),
62/// (d, a),
63/// (e, f),
64/// (b, e),
65/// (f, g),
66/// (g, h),
67/// (h, e),
68/// ]);
69/// // a ----> b ----> e ----> f
70/// // ^ | ^ |
71/// // | v | v
72/// // d <---- c h <---- g
73///
74/// let expected_res: HashMap<NodeIndex, usize> = [
75/// (a, 3),
76/// (b, 0),
77/// (c, 1),
78/// (d, 2),
79/// (e, 1),
80/// (f, 2),
81/// (g, 3),
82/// (h, 4),
83/// ].iter().cloned().collect();
84/// let res = dijkstra(&graph, b, None, |_| 1);
85/// assert_eq!(res, expected_res);
86/// // z is not inside res because there is not path from b to z.
87/// ```
88pub fn dijkstra<G, F, K>(
89 graph: G,
90 start: G::NodeId,
91 goal: Option<G::NodeId>,
92 edge_cost: F,
93) -> HashMap<G::NodeId, K>
94where
95 G: IntoEdges + Visitable,
96 G::NodeId: Eq + Hash,
97 F: FnMut(G::EdgeRef) -> K,
98 K: Measure + Copy,
99{
100 with_dynamic_goal(graph, start, |node| goal.as_ref() == Some(node), edge_cost).scores
101}
102
103/// Return value of [`with_dynamic_goal`].
104pub struct AlgoResult<N, K> {
105 /// A [`struct@hashbrown::HashMap`] that maps `NodeId` to path cost.
106 pub scores: HashMap<N, K>,
107 /// The goal node that terminated the search, if any was found.
108 pub goal_node: Option<N>,
109}
110
111/// Dijkstra's shortest path algorithm with a dynamic goal.
112///
113/// This algorithm is identical to [`dijkstra`],
114/// but allows matching multiple goal nodes, whichever is reached first.
115/// A node is considered a goal if `goal_fn` returns `true` for it.
116///
117/// See the [`dijkstra`] function for more details.
118///
119/// # Example
120/// ```rust
121/// use petgraph::Graph;
122/// use petgraph::algo::dijkstra;
123/// use petgraph::prelude::*;
124/// use hashbrown::HashMap;
125///
126/// let mut graph: Graph<(), (), Directed> = Graph::new();
127/// let a = graph.add_node(()); // node with no weight
128/// let b = graph.add_node(());
129/// let c = graph.add_node(());
130/// let d = graph.add_node(());
131/// let e = graph.add_node(());
132/// let f = graph.add_node(());
133/// let g = graph.add_node(());
134/// let h = graph.add_node(());
135/// // z will be in another connected component
136/// let z = graph.add_node(());
137///
138/// graph.extend_with_edges(&[
139/// (a, b),
140/// (b, c),
141/// (c, d),
142/// (d, a),
143/// (e, f),
144/// (b, e),
145/// (f, g),
146/// (g, h),
147/// (h, e),
148/// ]);
149/// // a ----> b ----> e ----> f
150/// // ^ | ^ |
151/// // | v | v
152/// // d <---- c h <---- g
153///
154/// let expected_res: HashMap<NodeIndex, usize> = [
155/// (b, 0),
156/// (c, 1),
157/// (d, 2),
158/// (e, 1),
159/// (f, 2),
160/// ].iter().cloned().collect();
161/// let res = dijkstra::with_dynamic_goal(&graph, b, |&node| node == d || node == f, |_| 1);
162/// assert_eq!(res.scores, expected_res);
163/// assert!(res.goal_node == Some(d) || res.goal_node == Some(f));
164/// ```
165pub fn with_dynamic_goal<G, GoalFn, CostFn, K>(
166 graph: G,
167 start: G::NodeId,
168 mut goal_fn: GoalFn,
169 mut edge_cost: CostFn,
170) -> AlgoResult<G::NodeId, K>
171where
172 G: IntoEdges + Visitable,
173 G::NodeId: Eq + Hash,
174 GoalFn: FnMut(&G::NodeId) -> bool,
175 CostFn: FnMut(G::EdgeRef) -> K,
176 K: Measure + Copy,
177{
178 let mut visited = graph.visit_map();
179 let mut scores = HashMap::new();
180 //let mut predecessor = HashMap::new();
181 let mut visit_next = BinaryHeap::new();
182 let zero_score = K::default();
183 scores.insert(start, zero_score);
184 visit_next.push(MinScored(zero_score, start));
185 let mut goal_node = None;
186 while let Some(MinScored(node_score, node)) = visit_next.pop() {
187 if visited.is_visited(&node) {
188 continue;
189 }
190 if goal_fn(&node) {
191 goal_node = Some(node);
192 break;
193 }
194 for edge in graph.edges(node) {
195 let next = edge.target();
196 if visited.is_visited(&next) {
197 continue;
198 }
199 let next_score = node_score + edge_cost(edge);
200 match scores.entry(next) {
201 Occupied(ent) => {
202 if next_score < *ent.get() {
203 *ent.into_mut() = next_score;
204 visit_next.push(MinScored(next_score, next));
205 //predecessor.insert(next.clone(), node.clone());
206 }
207 }
208 Vacant(ent) => {
209 ent.insert(next_score);
210 visit_next.push(MinScored(next_score, next));
211 //predecessor.insert(next.clone(), node.clone());
212 }
213 }
214 }
215 visited.visit(node);
216 }
217 AlgoResult { scores, goal_node }
218}
219
220/// Bidirectional Dijkstra's shortest path algorithm.
221///
222/// Compute the length of the shortest path from `start` to `target`.
223///
224/// Bidirectional Dijkstra has the same time complexity as standard [`Dijkstra`][dijkstra]. However, because it
225/// searches simultaneously from both the start and goal nodes, meeting in the middle, it often
226/// explores roughly half the nodes that regular [`Dijkstra`][dijkstra] would explore. This is especially the case
227/// when the path is long relative to the graph size or when working with sparse graphs.
228///
229/// However, regular [`Dijkstra`][dijkstra] may be preferable when you need the shortest paths from the start node
230/// to multiple goals or when the start and goal are relatively close to each other.
231///
232/// The function `edge_cost` should return the cost for a particular edge, which is used
233/// to compute path costs. Edge costs must be non-negative.
234///
235/// # Arguments
236/// * `graph`: weighted graph.
237/// * `start`: the start node.
238/// * `goal`: the goal node.
239/// * `edge_cost`: closure that returns the cost of a particular edge.
240///
241/// # Returns
242/// * `Some(K)` - the total cost from start to finish, if one was found.
243/// * `None` - if such a path was not found.
244///
245/// # Complexity
246/// * Time complexity: **O((|V|+|E|)log(|V|))**.
247/// * Auxiliary space: **O(|V|+|E|)**.
248///
249/// where **|V|** is the number of nodes and **|E|** is the number of edges.
250///
251/// # Example
252/// ```rust
253/// use petgraph::Graph;
254/// use petgraph::algo::bidirectional_dijkstra;
255/// use petgraph::prelude::*;
256/// use hashbrown::HashMap;
257///
258/// let mut graph: Graph<(), (), Directed> = Graph::new();
259/// let a = graph.add_node(());
260/// let b = graph.add_node(());
261/// let c = graph.add_node(());
262/// let d = graph.add_node(());
263/// let e = graph.add_node(());
264/// let f = graph.add_node(());
265/// let g = graph.add_node(());
266/// let h = graph.add_node(());
267///
268/// graph.extend_with_edges(&[
269/// (a, b),
270/// (b, c),
271/// (c, d),
272/// (d, a),
273/// (e, f),
274/// (b, e),
275/// (f, g),
276/// (g, h),
277/// (h, e),
278/// ]);
279/// // a ----> b ----> e ----> f
280/// // ^ | ^ |
281/// // | v | v
282/// // d <---- c h <---- g
283///
284/// let result = bidirectional_dijkstra(&graph, a, g, |_| 1);
285/// assert_eq!(result, Some(4));
286/// ```
287pub fn bidirectional_dijkstra<G, F, K>(
288 graph: G,
289 start: G::NodeId,
290 goal: G::NodeId,
291 mut edge_cost: F,
292) -> Option<K>
293where
294 G: Visitable + IntoEdgesDirected,
295 G::NodeId: Eq + Hash,
296 F: FnMut(G::EdgeRef) -> K,
297 K: Measure + Copy,
298{
299 let mut forward_visited = graph.visit_map();
300 let mut forward_distance = HashMap::new();
301 forward_distance.insert(start, K::default());
302
303 let mut backward_visited = graph.visit_map();
304 let mut backward_distance = HashMap::new();
305 backward_distance.insert(goal, K::default());
306
307 let mut forward_heap = BinaryHeap::new();
308 let mut backward_heap = BinaryHeap::new();
309
310 forward_heap.push(MinScored(K::default(), start));
311 backward_heap.push(MinScored(K::default(), goal));
312
313 let mut best_value = None;
314
315 while !forward_heap.is_empty() && !backward_heap.is_empty() {
316 let MinScored(_, u) = forward_heap.pop().unwrap();
317 let MinScored(_, v) = backward_heap.pop().unwrap();
318
319 forward_visited.visit(u);
320 backward_visited.visit(v);
321
322 let distance_to_u = forward_distance[&u];
323 let distance_to_v = backward_distance[&v];
324
325 for edge in graph.edges_directed(u, Direction::Outgoing) {
326 let x = edge.target();
327 let current_edge_cost = edge_cost(edge);
328
329 if !forward_visited.is_visited(&x) {
330 let next_score = distance_to_u + current_edge_cost;
331
332 match forward_distance.entry(x) {
333 Occupied(entry) => {
334 if next_score < *entry.get() {
335 *entry.into_mut() = next_score;
336 forward_heap.push(MinScored(next_score, x));
337 }
338 }
339 Vacant(entry) => {
340 entry.insert(next_score);
341 forward_heap.push(MinScored(next_score, x));
342 }
343 }
344 }
345
346 if !backward_visited.is_visited(&x) {
347 continue;
348 }
349
350 let potential_best_value = distance_to_u + current_edge_cost + backward_distance[&x];
351
352 let improves_best_value = match best_value {
353 None => true,
354 Some(current_best_value) => potential_best_value < current_best_value,
355 };
356
357 if improves_best_value {
358 best_value = Some(potential_best_value);
359 }
360 }
361
362 for edge in graph.edges_directed(v, Direction::Incoming) {
363 let x = edge.source();
364 let edge_cost = edge_cost(edge);
365
366 if !backward_visited.is_visited(&x) {
367 let next_score = distance_to_v + edge_cost;
368
369 match backward_distance.entry(x) {
370 Occupied(entry) => {
371 if next_score < *entry.get() {
372 *entry.into_mut() = next_score;
373 backward_heap.push(MinScored(next_score, x));
374 }
375 }
376 Vacant(entry) => {
377 entry.insert(next_score);
378 backward_heap.push(MinScored(next_score, x));
379 }
380 }
381 }
382
383 if !forward_visited.is_visited(&x) {
384 continue;
385 }
386
387 let potential_best_value = distance_to_v + edge_cost + forward_distance[&x];
388
389 let improves_best_value = match best_value {
390 None => true,
391 Some(mu) => potential_best_value < mu,
392 };
393
394 if improves_best_value {
395 best_value = Some(potential_best_value);
396 }
397 }
398
399 if let Some(best_value) = best_value {
400 if distance_to_u + distance_to_v >= best_value {
401 return Some(best_value);
402 }
403 }
404 }
405
406 None
407}