cp_library_rs/graph/
dijkstra.rs

1//! ダイクストラ法
2
3use std::cmp::Reverse;
4use std::collections::BinaryHeap;
5
6use num_traits::{Bounded, Zero};
7
8/// Dijkstra法
9/// - グラフ`graph`が与えられたとき、スタート地点`s`から各頂点への最短路を求める
10///
11/// 戻り値
12/// - `prev`: 各頂点への最短路において、その頂点の直前の頂点
13/// - `dist`: スタート地点`s`から各頂点への最短距離
14#[allow(clippy::ptr_arg)]
15pub fn dijkstra<T: Copy + Zero + Bounded + Ord>(
16    graph: &Vec<Vec<(usize, T)>>,
17    s: usize,
18) -> (Vec<Option<usize>>, Vec<T>) {
19    let n: usize = graph.len();
20    let mut prev = vec![None; n];
21    let mut dist = vec![T::max_value(); n];
22    let mut pq: BinaryHeap<Reverse<(T, usize)>> = BinaryHeap::new();
23    // 初期化
24    dist[s] = T::zero();
25    pq.push(Reverse((dist[s], s)));
26    // 更新
27    while let Some(Reverse((cost, u))) = pq.pop() {
28        if dist[u] < cost {
29            continue;
30        }
31        for &(v, weight) in &graph[u] {
32            if dist[v] > dist[u] + weight {
33                prev[v] = Some(u);
34                dist[v] = dist[u] + weight;
35                pq.push(Reverse((dist[v], v)));
36            }
37        }
38    }
39    (prev, dist)
40}
41
42/// 経路復元
43/// - スタート地点`s`からゴール地点`t`までの最短路を復元する
44///
45/// 戻り値
46/// - `Some(path)`: スタート地点`s`からゴール地点`t`までの最短路
47/// - `None`: sがダイクストラ法のスタート地点でない場合 | 最短路が存在しない場合
48#[allow(clippy::ptr_arg)]
49pub fn path_reconstruction(s: usize, t: usize, prev: &Vec<Option<usize>>) -> Option<Vec<usize>> {
50    if prev[s].is_some() || prev[t].is_none() {
51        return None;
52    }
53    // 経路復元
54    let mut cur = t;
55    let mut path = vec![t];
56    while cur != s {
57        cur = prev[cur]?;
58        path.push(cur);
59    }
60    path.reverse();
61    Some(path)
62}
cp_library_rs/graph/dijkstra.rs

cp_library_rs/graph/
dijkstra.rs
