Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- fn find_path(edges: Vec<((i32, i32), (i32, i32), i32)>, start: (i32, i32), end: (i32, i32)) -> Result<Vec<(i32, i32)>, &'static str> {
- #[derive(Copy, Clone)]
- struct Node {
- name: (i32, i32),
- weight: Option<i32>,
- source: Option<(i32, i32)>,
- }
- let mut info: HashMap<(i32, i32), Node> = HashMap::new();
- println!("L: {}, {:?}, {:?}", edges.len(), start, end);
- for edge in &edges {
- info.insert(edge.0, Node{name:edge.0, weight:None, source:None});
- info.insert(edge.1, Node{name:edge.1, weight:None, source:None});
- }
- info.insert(start, Node{name:start, weight:Some(0), source:None});
- let mut priority: Vec<&Node> = Vec::new();
- let mut node_edge: HashMap<(i32, i32), HashMap<(i32, i32), i32>> = HashMap::new();
- for (_key, node) in &info {
- node_edge.insert(node.name, HashMap::new());
- priority.push(node);
- }
- for edge in &edges {
- node_edge.get_mut(&edge.0).unwrap().insert(edge.1, edge.2);
- node_edge.get_mut(&edge.1).unwrap().insert(edge.0, edge.2);
- }
- while priority.len() > 0 {
- // Sort lowest weight to end of list
- priority.sort_by(|a, b| {let an = match a.weight { Some(r) => r, None => 99999i32, }; let bn = match b.weight { Some(r) => r, None => 99999i32, }; bn.cmp(&an)} );
- let scan = priority.pop().unwrap();
- if scan.name == end {
- println!("Done");
- println!("Weight: {:?}", scan.weight);
- break;
- }
- if scan.weight == None {
- break;
- }
- for (child, weight) in node_edge.get(&scan.name).unwrap() {
- let cw = scan.weight.unwrap() + weight;
- let node = info.get(&child).unwrap();
- if node.weight == None || cw < node.weight.unwrap() {
- let mut new_node = node.clone();
- new_node.weight = Some(cw);
- new_node.source = Some(scan.name);
- info.insert(new_node.name, new_node);
- }
- }
- }
- let mut node = info.get(&end).unwrap();
- if node.source == None {
- return Err("Failed to find path");
- }
- let mut entries: Vec<(i32, i32)> = Vec::new();
- while node.name != start {
- entries.push(node.name);
- node = info.get(&node.source.unwrap()).unwrap();
- }
- entries.push(start);
- entries.reverse();
- Ok(entries)
- }
Advertisement
Add Comment
Please, Sign In to add comment