penguin359

Dijkstra algorithm

Aug 12th, 2018
227
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Rust 2.41 KB | None | 0 0
  1. fn find_path(edges: Vec<((i32, i32), (i32, i32), i32)>, start: (i32, i32), end: (i32, i32)) -> Result<Vec<(i32, i32)>, &'static str> {
  2.    #[derive(Copy, Clone)]
  3.    struct Node {
  4.        name: (i32, i32),
  5.        weight: Option<i32>,
  6.        source: Option<(i32, i32)>,
  7.    }
  8.  
  9.    let mut info: HashMap<(i32, i32), Node> = HashMap::new();
  10.    println!("L: {}, {:?}, {:?}", edges.len(), start, end);
  11.    for edge in &edges {
  12.        info.insert(edge.0, Node{name:edge.0, weight:None, source:None});
  13.        info.insert(edge.1, Node{name:edge.1, weight:None, source:None});
  14.    }
  15.    info.insert(start, Node{name:start, weight:Some(0), source:None});
  16.    let mut priority: Vec<&Node> = Vec::new();
  17.    let mut node_edge: HashMap<(i32, i32), HashMap<(i32, i32), i32>> = HashMap::new();
  18.    for (_key, node) in &info {
  19.        node_edge.insert(node.name, HashMap::new());
  20.        priority.push(node);
  21.    }
  22.  
  23.    for edge in &edges {
  24.        node_edge.get_mut(&edge.0).unwrap().insert(edge.1, edge.2);
  25.        node_edge.get_mut(&edge.1).unwrap().insert(edge.0, edge.2);
  26.    }
  27.  
  28.    while priority.len() > 0 {
  29.        // Sort lowest weight to end of list
  30.        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)} );
  31.        let scan = priority.pop().unwrap();
  32.        if scan.name == end {
  33.            println!("Done");
  34.            println!("Weight: {:?}", scan.weight);
  35.            break;
  36.        }
  37.        if scan.weight == None {
  38.            break;
  39.        }
  40.        for (child, weight) in node_edge.get(&scan.name).unwrap() {
  41.            let cw = scan.weight.unwrap() + weight;
  42.            let node = info.get(&child).unwrap();
  43.            if node.weight == None || cw < node.weight.unwrap() {
  44.                let mut new_node = node.clone();
  45.                new_node.weight = Some(cw);
  46.                new_node.source = Some(scan.name);
  47.                info.insert(new_node.name, new_node);
  48.            }
  49.        }
  50.    }
  51.  
  52.    let mut node = info.get(&end).unwrap();
  53.    if node.source == None {
  54.        return Err("Failed to find path");
  55.    }
  56.  
  57.    let mut entries: Vec<(i32, i32)> = Vec::new();
  58.    while node.name != start {
  59.        entries.push(node.name);
  60.        node = info.get(&node.source.unwrap()).unwrap();
  61.    }
  62.    entries.push(start);
  63.    entries.reverse();
  64.  
  65.    Ok(entries)
  66. }
Advertisement
Add Comment
Please, Sign In to add comment