TWiki> FST Web>FstQuickTour>ShortestPathDoc (revision 7)EditAttach

ShortestPath

Description

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).

Usage

template<class Arc>
void ShortestPath(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, size_t n = 1);
doc [bad link?]
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)
 

Examples

A:

shortestpath1.jpg

(TropicalWeight)

Shortest path in A:

shortestpath2.jpg

2-shortest paths in A:

shortestpath3.jpg

Complexity

ShortestPath:

  • 1-shortest path:
    • Time: O(V log V + E)
    • Space: O(V)
  • n-shortest paths:
    • Time: O(V log V + n V + n E)
    • Space: O(n V)
where V = # of states and E = # of arcs.

References

-- CyrilAllauzen - 05 Jul 2007

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg shortestpath1.jpg r1 manage 9.4 K 2007-07-09 - 20:50 CyrilAllauzen shortest path input example
JPEGjpg shortestpath2.jpg r1 manage 6.1 K 2007-07-09 - 20:50 CyrilAllauzen 1-shortest path example
JPEGjpg shortestpath3.jpg r1 manage 18.5 K 2007-07-09 - 20:51 CyrilAllauzen 2-shortest path example
Edit | Attach | Watch | Print version | History: r11 | r9 < r8 < r7 < r6 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r7 - 2011-12-06 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback