petgraph/algo/
dijkstra.rs

Help
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 graph should be `Visitable` and implement `IntoEdges`. The function
19/// `edge_cost` should return the cost for a particular edge, which is used
20/// to compute path costs. Edge costs must be non-negative.
21///
22/// If `goal` is not `None`, then the algorithm terminates once the `goal` node's
23/// cost is calculated.
24///
25/// Returns a `HashMap` that maps `NodeId` to path cost.
26/// # Example
27/// ```rust
28/// use petgraph::Graph;
29/// use petgraph::algo::dijkstra;
30/// use petgraph::prelude::*;
31/// use hashbrown::HashMap;
32///
33/// let mut graph: Graph<(), (), Directed> = Graph::new();
34/// let a = graph.add_node(()); // node with no weight
35/// let b = graph.add_node(());
36/// let c = graph.add_node(());
37/// let d = graph.add_node(());
38/// let e = graph.add_node(());
39/// let f = graph.add_node(());
40/// let g = graph.add_node(());
41/// let h = graph.add_node(());
42/// // z will be in another connected component
43/// let z = graph.add_node(());
44///
45/// graph.extend_with_edges(&[
46///     (a, b),
47///     (b, c),
48///     (c, d),
49///     (d, a),
50///     (e, f),
51///     (b, e),
52///     (f, g),
53///     (g, h),
54///     (h, e),
55/// ]);
56/// // a ----> b ----> e ----> f
57/// // ^       |       ^       |
58/// // |       v       |       v
59/// // d <---- c       h <---- g
60///
61/// let expected_res: HashMap<NodeIndex, usize> = [
62///     (a, 3),
63///     (b, 0),
64///     (c, 1),
65///     (d, 2),
66///     (e, 1),
67///     (f, 2),
68///     (g, 3),
69///     (h, 4),
70/// ].iter().cloned().collect();
71/// let res = dijkstra(&graph, b, None, |_| 1);
72/// assert_eq!(res, expected_res);
73/// // z is not inside res because there is not path from b to z.
74/// ```
75pub fn dijkstra<G, F, K>(
76    graph: G,
77    start: G::NodeId,
78    goal: Option<G::NodeId>,
79    mut edge_cost: F,
80) -> HashMap<G::NodeId, K>
81where
82    G: IntoEdges + Visitable,
83    G::NodeId: Eq + Hash,
84    F: FnMut(G::EdgeRef) -> K,
85    K: Measure + Copy,
86{
87    let mut visited = graph.visit_map();
88    let mut scores = HashMap::new();
89    //let mut predecessor = HashMap::new();
90    let mut visit_next = BinaryHeap::new();
91    let zero_score = K::default();
92    scores.insert(start, zero_score);
93    visit_next.push(MinScored(zero_score, start));
94    while let Some(MinScored(node_score, node)) = visit_next.pop() {
95        if visited.is_visited(&node) {
96            continue;
97        }
98        if goal.as_ref() == Some(&node) {
99            break;
100        }
101        for edge in graph.edges(node) {
102            let next = edge.target();
103            if visited.is_visited(&next) {
104                continue;
105            }
106            let next_score = node_score + edge_cost(edge);
107            match scores.entry(next) {
108                Occupied(ent) => {
109                    if next_score < *ent.get() {
110                        *ent.into_mut() = next_score;
111                        visit_next.push(MinScored(next_score, next));
112                        //predecessor.insert(next.clone(), node.clone());
113                    }
114                }
115                Vacant(ent) => {
116                    ent.insert(next_score);
117                    visit_next.push(MinScored(next_score, next));
118                    //predecessor.insert(next.clone(), node.clone());
119                }
120            }
121        }
122        visited.visit(node);
123    }
124    scores
125}
petgraph/algo/dijkstra.rs

petgraph/algo/
dijkstra.rs
