dsalgo/
dijkstra_sparse_predecessors.rs

1use crate::{
2    dijkstra_sparse_queue::DijkstraSparseQueue,
3    general_dijkstra_sparse::general_dijkstra_sparse,
4    graph::edge::{
5        To,
6        Weight,
7    },
8};
9
10/// if 0-cost edges are included, result does not always become a DAG.
11
12pub fn dijkstra_sparse_predecessors<E, Q>(
13    sparse_graph: &[Vec<E>],
14    src: usize,
15) -> Vec<Vec<usize>>
16where
17    E: To<V = usize> + Weight<u64>,
18    Q: DijkstraSparseQueue,
19{
20    general_dijkstra_sparse::<_, _, _, Q>(
21        sparse_graph,
22        &|dist, pre: &mut Vec<Vec<usize>>, u, e: &E| {
23            let v = *e.to();
24
25            let dv = dist[u].unwrap() + e.weight();
26
27            if let Some(prev_dv) = dist[v] {
28                if dv < prev_dv {
29                    pre[v] = vec![u];
30                } else if dv == prev_dv {
31                    pre[v].push(u);
32                }
33            } else {
34                pre[v] = vec![u];
35            }
36        },
37        vec![vec![]; sparse_graph.len()],
38        src,
39    )
40    .1
41}
42
43// TODO
44#[cfg(test)]
45
46mod tests {
47
48    #[test]
49
50    fn test() {}
51}
dsalgo/dijkstra_sparse_predecessors.rs

dsalgo/
dijkstra_sparse_predecessors.rs
