Function rustfst::algorithms::all_pairs_shortest_distance

pub fn all_pairs_shortest_distance<W, F>(fst: &F) -> Result<Vec<Vec<W>>> where
    F: Fst<W> + ExpandedFst<W>,
    W: StarSemiring, 

This operation computes the shortest distance from each state to every other states. The shortest distance from p to q is the ⊕-sum of the weights of all the paths between p and q.

Example

let mut fst = VectorFst::<IntegerWeight>::new();
let s0 = fst.add_state();
let s1 = fst.add_state();
let s2 = fst.add_state();

fst.add_tr(s0, Tr::new(32, 23, 18, s1));
fst.add_tr(s0, Tr::new(32, 23, 21, s2));
fst.add_tr(s1, Tr::new(32, 23, 55, s2));

let dists = all_pairs_shortest_distance(&fst)?;

assert_eq!(dists, vec![
    vec![IntegerWeight::one(), IntegerWeight::new(18), IntegerWeight::new(18*55 + 21)],
    vec![IntegerWeight::zero(), IntegerWeight::one(), IntegerWeight::new(55)],
    vec![IntegerWeight::zero(), IntegerWeight::zero(), IntegerWeight::one()],
]);