petgraph/algo/
dijkstra.rs

1use alloc::collections::BinaryHeap;
2use core::hash::Hash;
3
4use hashbrown::hash_map::{
5    Entry::{Occupied, Vacant},
6    HashMap,
7};
8
9use crate::algo::Measure;
10use crate::scored::MinScored;
11use crate::visit::{EdgeRef, IntoEdges, VisitMap, Visitable};
12
13/// \[Generic\] 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    mut 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    let mut visited = graph.visit_map();
101    let mut scores = HashMap::new();
102    //let mut predecessor = HashMap::new();
103    let mut visit_next = BinaryHeap::new();
104    let zero_score = K::default();
105    scores.insert(start, zero_score);
106    visit_next.push(MinScored(zero_score, start));
107    while let Some(MinScored(node_score, node)) = visit_next.pop() {
108        if visited.is_visited(&node) {
109            continue;
110        }
111        if goal.as_ref() == Some(&node) {
112            break;
113        }
114        for edge in graph.edges(node) {
115            let next = edge.target();
116            if visited.is_visited(&next) {
117                continue;
118            }
119            let next_score = node_score + edge_cost(edge);
120            match scores.entry(next) {
121                Occupied(ent) => {
122                    if next_score < *ent.get() {
123                        *ent.into_mut() = next_score;
124                        visit_next.push(MinScored(next_score, next));
125                        //predecessor.insert(next.clone(), node.clone());
126                    }
127                }
128                Vacant(ent) => {
129                    ent.insert(next_score);
130                    visit_next.push(MinScored(next_score, next));
131                    //predecessor.insert(next.clone(), node.clone());
132                }
133            }
134        }
135        visited.visit(node);
136    }
137    scores
138}
petgraph/algo/dijkstra.rs

petgraph/algo/
dijkstra.rs
