ShortestPathDoc < FST

FST Web>FstQuickTour>ShortestPathDoc (2018-04-27, MichaelRiley) (raw view)

---+ !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 [[FstWeightRequirements][path]] property.  They also need to be left distributive as well for _n_ -shortest
with _n_ &gt; 1 (valid for =TropicalWeight=).

---++ Usage

|<verbatim>
template<class Arc>
void ShortestPath(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, size_t n = 1);
</verbatim> | 
| <verbatim>
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)
</verbatim> | 

---++ Examples

---+++ =A=:

%ATTACHURL%/shortestpath1.jpg

 (!TropicalWeight)

---+++ Shortest path in =A=:

%ATTACHURL%/shortestpath2.jpg

---+++ 2-shortest paths in =A=:

%ATTACHURL%/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. See [[FstEfficiency#AlgoSpecificEfficiency][here]] for more discussion on efficiency.


---++ Caveats

See [[FstEfficiency#AlgoSpecificEfficiency][here]] for a discussion on efficient usage.

---++ See Also

[[ShortestDistanceDoc][ShortestDistance]], [[FstAdvancedUsage#StateQueues][State Queues]]

---++ References

   * Mehryar Mohri. [[http://www.cs.nyu.edu/~mohri/postscript/jalc.ps][Semiring Framework and Algorithms for Shortest-Distance Problems]], _Journal of Automata, Languages and Combinatorics_, 7(3):321-350, 2002.
   * Mehryar Mohri and Michael Riley. [[http://www.cs.nyu.edu/~mohri/postscript/nbest.ps][An Efficient Algorithm for the n-best-strings problem]], In _Proceedings of the International Conference on Spoken Language Processing 2002 (ICSLP '02)_.



-- Main.CyrilAllauzen - 05 Jul 2007

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
jpg	shortestpath1.jpg	r1	manage	9.4 K	2007-07-09 - 20:50	CyrilAllauzen	shortest path input example
jpg	shortestpath2.jpg	r1	manage	6.1 K	2007-07-09 - 20:50	CyrilAllauzen	1-shortest path example
jpg	shortestpath3.jpg	r1	manage	18.5 K	2007-07-09 - 20:51	CyrilAllauzen	2-shortest path example

Topic revision: r11 - 2018-04-27 - MichaelRiley