TWiki
>
FST Web
>
FstQuickTour
>
ShortestDistanceDoc
(2019-11-05,
MichaelRiley
)
(raw view)
E
dit
A
ttach
---+ !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 ⊕-sum of the weights of all the paths between _p_ and _q_. The weights must be right (left) distributive if =reverse= is =false= (=true=) and _k_ -closed (i.e., <span style="text-decoration:overline">1</span> ⊕ _x_ ⊕ _x_ <sup>2</sup> ⊕ ... ⊕ _x_ <sup> _k_ +1</sup> = <span style="text-decoration:overline">1</span> ⊕ _x_ ⊕ _x_ <sup>2</sup> ⊕ ... ⊕ _x_ <sup> _k_ </sup>) (valid for non-negative =TropicalWeight=) or _k_ -closed when restricted to the automaton (valid for =TropicalWeight= with no negative weight cycles). ---++ Usage |<verbatim> template<class Arc> void ShortestDistance(const Fst<Arc> &fst, vector<typename Arc::Weight> *distance, bool reverse = false); </verbatim> | | <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 (!TropicalWeight) ---+++ 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)_ * Cyclic: * Tropical semiring: _O(V log V + E)_ * General: exponential * Space: _O(V)_ where _V_ = # of states and _E_ = # of arcs. ---++ Caveats See [[FstEfficiency#AlgoSpecificEfficiency][here]] for a discussion on efficient usage. ---++ See Also [[ShortestPathDoc][ShortestPath]], [[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. -- Main.CyrilAllauzen - 05 Jul 2007
Attachments
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
E
dit
|
A
ttach
|
Watch
|
P
rint version
|
H
istory
: r10
<
r9
<
r8
<
r7
<
r6
|
B
acklinks
|
V
iew topic
|
WYSIWYG
|
M
ore topic actions
Topic revision: r10 - 2019-11-05
-
MichaelRiley
FST
Log In
or
Register
FST Web
Create New Topic
Index
Search
Changes
Notifications
Statistics
Preferences
Webs
Contrib
FST
Forum
GRM
Kernel
Main
Sandbox
TWiki
Main
Copyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback