dsalgo/
dijkstra_dense_i64_with_inf.rs

1pub fn dijkstra_dense(
2    inf: i64,
3    g: &[Vec<i64>],
4    src: usize,
5) -> Vec<i64> {
6    let n = g.len();
7
8    let mut dist = vec![inf; n];
9
10    dist[src] = 0;
11
12    let mut visited = vec![false; n];
13
14    // loop {
15    for _ in 0..n - 1 {
16        let mut u = n;
17
18        let mut du = inf;
19
20        for i in 0..n {
21            if visited[i] || dist[i] >= du {
22                continue;
23            }
24
25            u = i;
26
27            du = dist[i];
28        }
29
30        if u == n {
31            break;
32        }
33
34        visited[u] = true;
35
36        for v in 0..n {
37            if g[u][v] == inf {
38                continue;
39            }
40
41            dist[v] = dist[v].min(du + g[u][v]);
42        }
43    }
44
45    dist
46}
47
48#[cfg(test)]
49
50mod tests {
51
52    #[test]
53
54    fn test() {}
55}