haar_lib/mul_graph/
dijkstra.rs

1//! 頂点倍加グラフ上でのDijkstra法
2use std::{
3    cmp::Reverse,
4    collections::{BinaryHeap, HashMap, HashSet},
5    hash::Hash,
6    ops::Add,
7};
8
9pub use crate::mul_graph::MulGraph;
10use crate::num::{one_zero::Zero, traits::Unsigned};
11
12/// Dijkstra法
13pub fn dijkstra<V, W>(graph: &MulGraph<V, W>, src: &[V]) -> HashMap<V, W>
14where
15    V: Hash + Eq + Copy + Ord,
16    W: Copy + Ord + Zero + Add<Output = W> + Unsigned,
17{
18    let zero = W::zero();
19    let mut ret = HashMap::new();
20    let mut heap = BinaryHeap::new();
21    let mut check = HashSet::new();
22
23    for &u in src {
24        ret.insert(u, zero);
25        heap.push(Reverse((zero, u)));
26    }
27
28    while let Some(Reverse((d, u))) = heap.pop() {
29        if check.contains(&u) {
30            continue;
31        }
32        check.insert(u);
33
34        for e in graph.neighbours_of(u) {
35            let to = e.to;
36            let cost = e.weight;
37
38            match ret.get(&to) {
39                Some(&d2) if d2 <= d + cost => {}
40                _ => {
41                    let d = d + cost;
42                    ret.insert(to, d);
43                    if !check.contains(&to) {
44                        heap.push(Reverse((d, to)));
45                    }
46                }
47            }
48        }
49    }
50
51    ret
52}
haar_lib/mul_graph/dijkstra.rs

haar_lib/mul_graph/
dijkstra.rs
