This operation produces an FST containing the n -shortest paths in the input FST. The n -shortest paths are the n -lowest weight paths w.r.t. the natural semiring order. The single path that can be read from the ith of at most n transitions leaving the initial state of the resulting FST is the ith shortest path.
The weights need to be right distributive and have the path property. They also need to be left distributive as well for n -shortest
with n > 1 (valid for TropicalWeight
).
template<class Arc> void ShortestPath(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, size_t n = 1); |
fstshortestpath [--opts] a.fst out.fst --nshortest: type = int64, default = 1 Return N-shortest paths --unique: default = false Return only distinct strings (NB: must be acceptor; epsilons treated as regular symbols) |
A
:
(TropicalWeight)
A
:
A
:
ShortestPath:
See here for a discussion on efficient usage.
ShortestDistance, State Queues
-- CyrilAllauzen - 05 Jul 2007
I | Attachment | History | Action | Size | Date | Who | Comment |
---|---|---|---|---|---|---|---|
jpg | shortestpath2.jpg | r1 | manage | 6.1 K | 2007-07-09 - 20:50 | CyrilAllauzen | 1-shortest path example |
jpg | shortestpath1.jpg | r1 | manage | 9.4 K | 2007-07-09 - 20:50 | CyrilAllauzen | shortest path input example |
jpg | shortestpath3.jpg | r1 | manage | 18.5 K | 2007-07-09 - 20:51 | CyrilAllauzen | 2-shortest path example |