Struct ShortestPathWithParent 

pub struct ShortestPathWithParent<G, S, P = RecordParent>
where
    G: Graph + VertexMap<S::T>,
    S: ShortestPathSemiRing,
    P: ParentPolicy<G>,
{
    pub dist: <G as VertexMap<S::T>>::Vmap,
    pub parent: P::State,
}

Fields

dist: <G as VertexMap<S::T>>::Vmap

parent: P::State

Implementations

impl<G, S> ShortestPathWithParent<G, S, RecordParent>

where G: Graph + VertexMap<S::T> + VertexMap<Option<<G as Graph>::Vertex>>, S: ShortestPathSemiRing,

pub fn path_to(&self, graph: &G, target: G::Vertex) -> Option<Vec<G::Vertex>>

Examples found in repository

crates/library_checker/src/graph/shortest_path.rs (line 12)

pub fn shortest_path(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m, s, t, (g, c): @DirectedGraphScanner::<usize, u64>::new(n, m));
    let sp = g
        .standard_sp_additive()
        .with_parent()
        .dijkstra_to([s], t, |eid| c[eid]);
    if let Some(path) = sp.path_to(&g, t) {
        pp!(sp.dist[t], path.len() - 1; @it2d path.windows(2));
    } else {
        pp!(-1);
    }
}