day 16

1 files changed, 30 insertions, 0 deletions

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<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,