1 use std::collections::hash_map::Entry::{Occupied, Vacant};
2 use std::collections::{BinaryHeap, HashMap};
3
4 use std::hash::Hash;
5
6 use crate::algo::Measure;
7 use crate::scored::MinScored;
8 use 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 /// ```
dijkstra<G, F, K>( graph: G, start: G::NodeId, goal: Option<G::NodeId>, mut edge_cost: F, ) -> HashMap<G::NodeId, K> where G: IntoEdges + Visitable, G::NodeId: Eq + Hash, F: FnMut(G::EdgeRef) -> K, K: Measure + Copy,72 pub 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>
78 where
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 }
123