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}
petgraph/algo/dijkstra.rs

petgraph/algo/
dijkstra.rs
