dijkstra · Rust

tritium demo dijkstra
transcript · python · c · rust

// TRITIUM-PROVENANCE sha256=cecf307e190155d45c2cc7a93a750de16f8670bcbb0f247d9967748079f4e335 lang=rust
// TRITIUM-HEIGHT high=1.00 mid=0.00 low=0.00
fn dist_init(dist: &mut [i64], n: i64, start: i64, inf: i64) -> i64 {

    let mut i = 0;
    while i < n {
        dist[i as usize] = inf;
        i += 1;
    }
    dist[start as usize] = 0;
    0
}

fn heap_push(heap_dist: &mut [i64], heap_node: &mut [i64], n: i64, d: i64, u: i64) -> i64 {
    let mut parent = 0;

    let mut i = n;
    heap_dist[i as usize] = d;
    heap_node[i as usize] = u;
    while i > 0 {
        parent = (i - 1) / 2;
        if heap_dist[i as usize] >= heap_dist[parent as usize] {
            break;
        }
        let mut swap = heap_dist[i as usize];
        heap_dist[i as usize] = heap_dist[parent as usize];
        heap_dist[parent as usize] = swap;
        let mut tmp_node = heap_node[i as usize];
        heap_node[i as usize] = heap_node[parent as usize];
        heap_node[parent as usize] = tmp_node;
        i = parent;
    }
    n + 1
}

fn heap_min_d(heap_dist: &[i64], heap_node: &[i64], n: i64) -> i64 {

    heap_dist[0]
}

fn heap_min_u(heap_dist: &[i64], heap_node: &[i64], n: i64) -> i64 {

    heap_node[0]
}

fn heap_pop(heap_dist: &mut [i64], heap_node: &mut [i64], n: i64) -> i64 {
    let mut left = 0;
    let mut right = 0;
    let mut best = 0;

    let mut diff = n - 1;
    heap_dist[0] = heap_dist[diff as usize];
    heap_node[0] = heap_node[diff as usize];
    let mut i = 0;
    diff -= 1;
    loop {
        left = (i * 2) + 1;
        right = left + 1;
        if left > diff {
            break;
        }
        best = left;
        if right <= diff {
            if heap_dist[right as usize] < heap_dist[left as usize] {
                best = right;
            }
        }
        if heap_dist[i as usize] <= heap_dist[best as usize] {
            break;
        }
        let mut swap = heap_dist[i as usize];
        heap_dist[i as usize] = heap_dist[best as usize];
        heap_dist[best as usize] = swap;
        let mut tmp_node = heap_node[i as usize];
        heap_node[i as usize] = heap_node[best as usize];
        heap_node[best as usize] = tmp_node;
        i = best;
    }
    n - 1
}

fn list_get(a: &[i64], i: i64) -> i64 {
    if i < 0 {
        return 0;
    }
    let i = i as usize;
    if i >= a.len() { 0 } else { a[i] }
}

fn stale_visit(dist: &[i64], u: i64, d: i64) -> i64 {

    if d > list_get(dist, u) { 1 } else { 0 }
}

fn relax_edge(dist: &mut [i64], heap_dist: &mut [i64], heap_node: &mut [i64], heap_len: i64, u: i64, v: i64, w: i64) -> i64 {

    let mut heap_len_2 = heap_len;
    let mut sum = dist[u as usize] + w;
    if sum < dist[v as usize] {
        dist[v as usize] = sum;
        heap_len_2 = heap_push(heap_dist, heap_node, heap_len_2, sum, v);
    }
    heap_len_2
}

fn edge_relax(dist: &mut [i64], heap_dist: &mut [i64], heap_node: &mut [i64], heap_len: i64, dest: &[i64], weight: &[i64], e: i64, u: i64) -> i64 {

    relax_edge(dist, heap_dist, heap_node, heap_len, u, list_get(dest, e), list_get(weight, e))
}

fn scan_neighbors(dist: &mut [i64], heap_dist: &mut [i64], heap_node: &mut [i64], heap_len: i64, dest: &[i64], weight: &[i64], offsets: &[i64], u: i64) -> i64 {

    let mut heap_len_2 = heap_len;
    let mut idx = list_get(offsets, u);
    while idx < list_get(offsets, u + 1) {
        heap_len_2 = edge_relax(dist, heap_dist, heap_node, heap_len_2, dest, weight, idx, u);
        idx += 1;
    }
    heap_len_2
}

fn dijkstra(n: i64, offsets: &[i64], dest: &[i64], weight: &[i64], start: i64, dist: &mut [i64], heap_dist: &mut [i64], heap_node: &mut [i64]) -> i64 {
    let mut u = 0;

    let mut inf = 1000000000;
    dist_init(dist, n, start, inf);
    let mut heap_len = heap_push(heap_dist, heap_node, 0, 0, start);
    while heap_len > 0 {
        u = heap_min_u(heap_dist, heap_node, heap_len);
        heap_len = heap_pop(heap_dist, heap_node, heap_len);
        if stale_visit(dist, u, heap_min_d(heap_dist, heap_node, heap_len)) != 1 {
            heap_len = scan_neighbors(dist, heap_dist, heap_node, heap_len, dest, weight, offsets, u);
        }
    }
    0
}