A rust dijkstra implementation

dijkstra.rs

use std::collections::VecDeque;
const INF: u32 = std::u32::MAX;

fn extract_min(graph: &Graph, queue: &mut Vec<u32>) -> u32 {
    let mut min: u32 = INF;
    let mut min_idx: usize = 0;
    let _queue = queue.clone();

    for (idx, node_id) in _queue.iter().enumerate() {
        let n = graph.verts.iter().find(|&n| n.id == *node_id).unwrap();
        if n.key < min {
            min = n.key;
            min_idx = idx;
        }
    }

    let min_node_id = queue[min_idx];
    queue.remove(min_idx);
    return min_node_id;
}

fn relax(graph: &Graph, u: u32, v: u32, w: u32) -> u32 {
    let u_key = graph.verts[u as usize].key;
    let v_key = graph.verts[v as usize].key;
    if v_key > (w + u_key) || v_key == INF {
        return w + u_key;
    }
    return 0;
}

fn dijkstra(mut graph: Graph, source: u32) -> Vec<Branch> {
    let mut s: Vec<u32> = Vec::new();
    graph.verts[source as usize].key = 0;
    let mut tree: VecDeque<Branch> = VecDeque::new();

    let mut q: Vec<u32> = graph.verts
        .iter()
        .map(|&n| n.id)
        .collect();

    while q.len() > 0 {
        let u = extract_min(&graph, &mut q);
        s.push(u);
        for v in graph.adj_oriented(u) {
            let w = graph.branch_oriented(u, v).unwrap().w;
            let new_cost = relax(&graph, u, v, w);
            if new_cost != 0 {
                graph.verts[v as usize].key = new_cost;
                graph.verts[v as usize].parent = u as i32;
            }
        }
    }

    for i in (0..graph.verts.len()).rev() {
        let node = graph.verts[i];
        if node.parent >= 0 {
            let branch = graph.branch_oriented(node.parent as u32, node.id).unwrap();
            tree.push_front(Branch::new(node.parent as u32, node.id, branch.w));
        }
    }

    return Vec::from(tree);
}

pub fn test_dijkstra() {
    let mut nodes = Vec::<Node>::new();

    for i in 0..5 {
        nodes.push(Node::new(i, INF, -1));
    }

    println!("\n===================\n");
    println!("Initial graph:\n");

    let mut graph = Graph::new(nodes);
    graph.insert(0, 1, 5);
    graph.insert(0, 2, 10);
    graph.insert(1, 2, 3);
    graph.insert(1, 3, 9);
    graph.insert(1, 4, 2);
    graph.insert(2, 1, 2);
    graph.insert(2, 3, 1);
    graph.insert(3, 4, 4);
    graph.insert(4, 3, 6);
    graph.insert(4, 0, 7);


    for b in &graph.edges {
        println!("branch: ({})---[{}]---({})", b.x, b.w, b.y);
    }

    println!("\n===================\n");
    println!("SST graph:\n");

    let tree = dijkstra(graph, 0);
    for b in &tree {
        println!("branch: ({})---[{}]---({})", b.x, b.w, b.y);
    }
}