petgraph/algo/
dijkstra.rs

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

petgraph/algo/
dijkstra.rs
