Struct Dijkstra

pub struct Dijkstra<'a, W, E> { /* private fields */ }

ダイクストラ法

Implementations

impl<'a, E> Dijkstra<'a, E::Weight, E>

where E: EdgeTrait, E::Weight: Add<Output = E::Weight> + Copy + Ord + Zero + Unsigned,

pub fn new(g: &'a Graph<impl Direction, E>, src: &[usize]) -> Self

グラフg上で、始点から各頂点への最短パスを求める。

Time complexity $O((E + V) \log V)$

pub fn min_dist_table(&self) -> &[Option<E::Weight>]

最短距離の配列への参照を返す。

pub fn min_dist_to(&self, to: usize) -> Option<E::Weight>

toへの最短距離を返す。 到達不可能ならば、Noneを返す。

pub fn min_path_to(&self, to: usize) -> Option<Vec<&E>>

toへの最短パスを返す。 到達不可能ならば、Noneを返す。