dsalgo/
dijkstra_sparse_option.rs

1/// T is a numeric type.
2/// if there are negative edges,
3/// the correctness of the answer is not guaranteed.
4
5pub fn dijkstra<T>(
6    adj_list: &[Vec<(usize, T)>],
7    s: usize,
8) -> Vec<Option<T>>
9where
10    T: Copy + Ord + std::ops::Add<Output = T> + Default,
11{
12    use std::{
13        cmp::Reverse,
14        collections::BinaryHeap,
15    };
16
17    let g = adj_list;
18
19    let n = g.len();
20
21    let mut dist: Vec<Option<T>> = vec![None; n];
22
23    dist[s] = Some(T::default());
24
25    let mut q = BinaryHeap::new();
26
27    q.push(Reverse((dist[s].unwrap(), s)));
28
29    while let Some(Reverse((du, u))) = q.pop() {
30        if Some(du) > dist[u] {
31            continue;
32        }
33
34        for &(v, w) in &g[u] {
35            let dv = du + w;
36
37            if dist[v].is_some() && Some(dv) >= dist[v] {
38                continue;
39            }
40
41            dist[v] = Some(dv);
42
43            q.push(Reverse((dv, v)));
44        }
45    }
46
47    dist
48}
dsalgo/dijkstra_sparse_option.rs

dsalgo/
dijkstra_sparse_option.rs
