Dijkstra

dijkstra(graph: &Graph<T>, src: usize) where Graph<T> is a graph representation, T is a numeric data type, and src is an id of a source node. It returns a dist = Vec<Option<T>>, where dist[dst] is the length of a shortest path from src to dst if it exists, or None if dst is unreachable from src.

Example

#[allow(unused)]
use std::{cmp::*, collections::*, iter, mem::*, num::*, ops::*};

fn main() {
let mut graph: Vec<Vec<(usize, i64)>> = vec![vec![]; 4];
for (u, v, w) in [(0, 1, 5), (1, 2, 5), (1, 2, 15)] {
    graph[u].push((v, w));
    graph[v].push((u, w));
}
println!("{:?}", dijkstra(&graph, 0)); // [Some(0), Some(5), Some(10), None]
}

trait HasNz {
    type NzType;
    fn into_nz(self) -> Option<Self::NzType>;
    fn retrieve(nz: Self::NzType) -> Self;
}

macro_rules! impl_hasnz {
    ($($t:ty, $n:ty);*) => { $(
        impl HasNz for $t {
            type NzType = $n;
            fn into_nz(self) -> Option<$n> { <$n>::new(self) }
            fn retrieve(nz: $n) -> Self { nz.get() }
        }
    )* };
}

impl_hasnz!(i8, NonZeroI8; i16, NonZeroI16; i32, NonZeroI32; i64, NonZeroI64; i128, NonZeroI128; isize, NonZeroIsize);
impl_hasnz!(u8, NonZeroU8; u16, NonZeroU16; u32, NonZeroU32; u64, NonZeroU64; u128, NonZeroU128; usize, NonZeroUsize);

fn dijkstra<T>(graph: &[Vec<(usize, T)>], src: usize) -> Vec<Option<T>>
where
    T: Copy + From<u8> + Add<Output = T> + Sub<Output = T> + Eq + Ord + HasNz,
    <T as HasNz>::NzType: Copy,
{
    let mut dist: Vec<Option<T::NzType>> = vec![None; graph.len()];
    let mut heap: BinaryHeap<(Reverse<T>, usize)> = BinaryHeap::new();
    heap.push((Reverse(1.into()), src));

    while let Some((Reverse(curr_cost), curr)) = heap.pop() {
        if dist[curr].map_or(false, |x| T::retrieve(x) < curr_cost) {
            continue;
        }
        dist[curr] = curr_cost.into_nz();

        for &(next, weight) in graph[curr].iter() {
            let next_cost = curr_cost + weight;
            if dist[next].map_or(true, |x| T::retrieve(x) > next_cost) {
                dist[next] = next_cost.into_nz();
                heap.push((Reverse(next_cost), next));
            }
        }
    }

    dist.iter().map(|x| x.map(|x| T::retrieve(x) - 1.into())).collect()
}

Code

trait HasNz {
    type NzType;
    fn into_nz(self) -> Option<Self::NzType>;
    fn retrieve(nz: Self::NzType) -> Self;
}

macro_rules! impl_hasnz {
    ($($t:ty, $n:ty);*) => { $(
        impl HasNz for $t {
            type NzType = $n;
            fn into_nz(self) -> Option<$n> { <$n>::new(self) }
            fn retrieve(nz: $n) -> Self { nz.get() }
        }
    )* };
}

impl_hasnz!(i8, NonZeroI8; i16, NonZeroI16; i32, NonZeroI32; i64, NonZeroI64; i128, NonZeroI128; isize, NonZeroIsize);
impl_hasnz!(u8, NonZeroU8; u16, NonZeroU16; u32, NonZeroU32; u64, NonZeroU64; u128, NonZeroU128; usize, NonZeroUsize);

fn dijkstra<T>(graph: &[Vec<(usize, T)>], src: usize) -> Vec<Option<T>>
where
    T: Copy + From<u8> + Add<Output = T> + Sub<Output = T> + Eq + Ord + HasNz,
    <T as HasNz>::NzType: Copy,
{
    let mut dist: Vec<Option<T::NzType>> = vec![None; graph.len()];
    let mut heap: BinaryHeap<(Reverse<T>, usize)> = BinaryHeap::new();
    heap.push((Reverse(1.into()), src));

    while let Some((Reverse(curr_cost), curr)) = heap.pop() {
        if dist[curr].map_or(false, |x| T::retrieve(x) < curr_cost) {
            continue;
        }
        dist[curr] = curr_cost.into_nz();

        for &(next, weight) in graph[curr].iter() {
            let next_cost = curr_cost + weight;
            if dist[next].map_or(true, |x| T::retrieve(x) > next_cost) {
                dist[next] = next_cost.into_nz();
                heap.push((Reverse(next_cost), next));
            }
        }
    }

    dist.iter().map(|x| x.map(|x| T::retrieve(x) - 1.into())).collect()
}

Compact Version

The code is much compact, but the performance is slightly worse than the one above. This version seems to be approximately 10% slower, but none of the definitive tests have been done to check it.

fn dijkstra<T: Copy + From<u8> + Add<Output = T> + Eq + Ord>(graph: &[Vec<(usize, T)>], src: usize) -> Vec<Option<T>> {
    let mut dist: Vec<Option<T>> = vec![None; graph.len()];
    let mut heap: BinaryHeap<(Reverse<T>, usize)> = BinaryHeap::new();
    heap.push((Reverse(0.into()), src));

    while let Some((Reverse(curr_cost), curr)) = heap.pop() {
        if dist[curr].map_or(false, |x| x < curr_cost) {
            continue;
        }
        dist[curr] = Some(curr_cost);

        for &(next, weight) in graph[curr].iter() {
            let next_cost = curr_cost + weight;
            if dist[next].map_or(true, |x| x > next_cost) {
                dist[next] = Some(next_cost);
                heap.push((Reverse(next_cost), next));
            }
        }
    }
    dist
}