dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

use crate::{
    dijkstra_sparse_queue::DijkstraSparseQueue,
    general_dijkstra_sparse::general_dijkstra_sparse,
    graph::edge::{
        To,
        Weight,
    },
};

pub fn dijkstra_sparse<E, Q>(
    sparse_graph: &[Vec<E>],
    src: usize,
) -> Vec<Option<u64>>
where
    E: To<V = usize> + Weight<u64>,
    Q: DijkstraSparseQueue,
{
    general_dijkstra_sparse::<_, _, _, Q>(
        sparse_graph,
        &|_, _, _, _| {},
        (),
        src,
    )
    .0
}

#[cfg(test)]

mod tests {

    use super::*;
    use crate::dijkstra_queue_binary_heap_std::DijkstraQueueBinaryHeapStd;

    #[test]

    fn test() {
        let g = vec![
            vec![(0, 1, 1), (0, 2, 4)],
            vec![(1, 2, 2), (1, 3, 5)],
            vec![(2, 3, 1)],
            vec![],
        ];

        assert_eq!(
            dijkstra_sparse::<_, DijkstraQueueBinaryHeapStd>(&g, 0),
            vec![Some(0), Some(1), Some(3), Some(4)]
        );

        let g = vec![
            vec![(0, 1, 1), (0, 2, 4)],
            vec![(1, 2, 2)],
            vec![(2, 0, 1)],
            vec![(3, 1, 1), (3, 2, 5)],
        ];

        assert_eq!(
            dijkstra_sparse::<_, DijkstraQueueBinaryHeapStd>(&g, 1),
            vec![Some(3), Some(0), Some(2), None]
        );
    }
}