From add7534a2230149800a836a6a848f2143a5a5e2f Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Fri, 16 Dec 2022 05:07:14 -0500 Subject: day 16 --- src/graph.rs | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) (limited to 'src/graph.rs') diff --git a/src/graph.rs b/src/graph.rs index 9312e7c..f8fbf3c 100644 --- a/src/graph.rs +++ b/src/graph.rs @@ -9,6 +9,36 @@ where fn edges(&self, v: Vertex) -> Self::Edges; fn edge(&self, v: Vertex, e: Edge) -> (Vertex, u64); + fn dijkstra_full(&self, start: Vertex) -> HashMap { + 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 bool>( &self, start: Vertex, -- cgit v1.2.3-54-g00ecf