グラフ - 最短路 - ダイクストラ法
概要
BFS による最短ルートの探索アルゴリズム. ただし各辺の距離(コスト)は正であることを仮定している.
優先度付きヒープでBFSして \(O((E+V) \log V)\).
入出力
頂点 \(u\) から \(v\) へ, 距離(またはコスト)が \(c\) の枝があるときこれを neigh[u] = [(v, c)]
で表すような隣接リストを受け取る. 始点 s
から各頂点までの最小コストの列を返す.
/// Graph - Dijkstra
use crate::algebra::group_additive::*;
use crate::algebra::hyper::*;
pub fn dijkstra<Cost: Copy + AGroup + Ord>(
s: usize,
neigh: &Vec<Vec<(usize, Cost)>>,
) -> Vec<Hyper<Cost>> {
use std::cmp::Reverse;
use std::collections::BinaryHeap;
let n = neigh.len();
let mut d: Vec<Hyper<Cost>> = vec![Hyper::Inf; n];
let mut q = BinaryHeap::new();
d[s] = Hyper::Real(Cost::zero());
q.push((Reverse(d[s]), s));
while let Some((_, u)) = q.pop() {
for &(v, cost) in neigh[u].iter() {
if d[v] > d[u] + cost {
d[v] = d[u] + cost;
q.push((Reverse(d[v]), v));
}
}
}
d
}
#[cfg(test)]
mod test_dijkstra {
use crate::algebra::hyper::Hyper::*;
use crate::graph::shortest::dijkstra::*;
#[test]
fn test_circle_undirected() {
type Cost = i64;
let neigh: Vec<Vec<(usize, Cost)>> = vec![
vec![(1, 1), (4, 1)],
vec![(2, 1), (0, 1)],
vec![(3, 1), (1, 1)],
vec![(4, 1), (2, 1)],
vec![(0, 1), (3, 1)],
];
let expected = vec![Real(0), Real(1), Real(2), Real(2), Real(1)];
assert_eq!(dijkstra(0, &neigh), expected);
}
#[test]
fn test_circle_directed() {
type Cost = i64;
let neigh: Vec<Vec<(usize, Cost)>> = vec![
vec![(1, 1)],
vec![(2, 1)],
vec![(3, 1)],
vec![(4, 1)],
vec![(0, 1)],
];
let expected = vec![Real(0), Real(1), Real(2), Real(3), Real(4)];
assert_eq!(dijkstra(0, &neigh), expected);
}
#[test]
fn test_unconnected() {
type Cost = i64;
let neigh: Vec<Vec<(usize, Cost)>> = vec![
vec![(1, 1)],
vec![(0, 1)],
vec![(3, 1)],
vec![(4, 1)],
vec![(2, 1)],
];
let expected = vec![Real(0), Real(1), Inf, Inf, Inf];
assert_eq!(dijkstra(0, &neigh), expected);
}
}