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
|
use crate::prelude::*;
pub trait Graph<Vertex, Edge>
where
Vertex: std::hash::Hash + Clone + Copy + PartialEq + Eq + std::fmt::Debug,
{
type Edges: IntoIterator<Item = Edge>;
fn edges(&self, v: Vertex) -> Self::Edges;
fn edge(&self, v: Vertex, e: Edge) -> (Vertex, u64);
fn dijkstra_full(&self, start: Vertex) -> HashMap<Vertex, (Vertex, u64)> {
let mut to_visit = priority_queue::PriorityQueue::new();
let mut prev = HashMap::new();
prev.insert(start, (start, 0));
to_visit.push(start, std::cmp::Reverse(0));
while let Some((v, std::cmp::Reverse(distance))) = to_visit.pop() {
for e in self.edges(v) {
let (next, weight) = self.edge(v, e);
let visited = prev.contains_key(&next);
let new_distance = distance + weight;
if to_visit.get(&next).is_some() {
prev.insert(next, (v, new_distance));
if new_distance < to_visit.get_priority(&next).unwrap().0
{
to_visit.change_priority(
&next,
std::cmp::Reverse(new_distance),
);
}
} else {
if !visited {
prev.insert(next, (v, new_distance));
to_visit.push(next, std::cmp::Reverse(new_distance));
}
}
}
}
prev
}
fn dijkstra<F: Fn(Vertex) -> bool>(
&self,
start: Vertex,
end: F,
) -> (u64, Vec<Vertex>) {
let mut to_visit = priority_queue::PriorityQueue::new();
let mut prev = HashMap::new();
prev.insert(start, start);
to_visit.push(start, std::cmp::Reverse(0));
while let Some((v, std::cmp::Reverse(distance))) = to_visit.pop() {
if end(v) {
let mut path = vec![v];
let mut cur = v;
while let Some(next) = prev.get(&cur) {
if *next == cur {
break;
}
path.insert(0, *next);
cur = *next;
}
return (distance, path);
}
for e in self.edges(v) {
let (next, weight) = self.edge(v, e);
let visited = prev.contains_key(&next);
let new_distance = distance + weight;
if to_visit.get(&next).is_some() {
prev.insert(next, v);
if new_distance < to_visit.get_priority(&next).unwrap().0
{
to_visit.change_priority(
&next,
std::cmp::Reverse(new_distance),
);
}
} else {
if !visited {
prev.insert(next, v);
to_visit.push(next, std::cmp::Reverse(new_distance));
}
}
}
}
unreachable!()
}
}
|
