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