(r4) ShortestDistanceDoc < FST

FST Web>FstQuickTour>ShortestDistanceDoc (revision 4) (raw view)~~EditAttach~~

---+ !ShortestDistance

---++ Description

This operation computes the shortest distance from the initial state to every state (when =reverse= is =false=) or
from every state to the final states (when =reverse= is =true=). The _shortest distance_ from _p_ to _q_ is the 
&oplus;-sum of the weights of all the paths between _p_ and _q_.

The weights must must be right (left) distributive if =reverse= is =false= (=true=) 
and _k_ -closed (i.e., <span style="text-decoration:overline">1</span> &oplus; _x_ &oplus; _x_ <sup>2</sup> &oplus; ... &oplus; _x_ <sup> _k_ +1</sup> = <span style="text-decoration:overline">1</span> &oplus; _x_ &oplus; _x_ <sup>2</sup> &oplus; ... &oplus; _x_ <sup> _k_ </sup>) (valid for =TropicalWeight=).

---++ Usage

|<verbatim>
template<class Arc>
void ShortestDistance(const Fst<Arc> &fst, vector<typename Arc::Weight> *distance, bool reverse = false);
</verbatim> |  %DOX{namespacefst.html#ShortestDistance[%H%]}% |
| <verbatim>
fstshortestdistance [--opts] a.fst [distance.txt]
    --reverse: type = bool, default = false
      Perform in the reverse direction
</verbatim> ||

---++ Examples

---+++ =A=, over the tropical semiring:

%ATTACHURL%/shortestdistance.jpg

---+++ Shortest distance from the initial state

|*State* | *Distance*|
| =0= | =0= |
| =1= | =3= |
| =2= | =5= |
| =3= | =7= |

<verbatim>
ShortestDistance(A, &distance);
fstshortestdistance a.fst
</verbatim>

---+++ Shortest distance to the final states

|*State* | *Distance*|
| =0= | =10= |
| =1= | =7= |
| =2= | =7= |
| =3= | =3= |

<verbatim>
ShortestDistance(A, &distance, true);
fstshortestdistance --reverse A.fst
</verbatim>

---++ Complexity

=ShortestDistance:=
   * TIme:
      *  Acyclic: _O(V + E)_
      *  Tropical semiring:  _O(V log V  + E)_
      *  General: _exponential_ 
   * Space: _O(V)_ 
where _V_ = # of states and _E_ = # of arcs.


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



-- Main.CyrilAllauzen - 05 Jul 2007

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
jpg	shortestdistance.jpg	r1	manage	9.4 K	2007-07-09 - 20:31	CyrilAllauzen	Shortest distance input example

Topic revision: r4 - 2007-07-11 - MichaelRiley