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 must be right (left) distributive if
reverse
is
false
(
true
)
and
k -closed (i.e.,
1 ⊕
x ⊕
x 2 ⊕ ... ⊕
x k +1 =
1 ⊕
x ⊕
x 2 ⊕ ... ⊕
x k ).
Usage
template<class Arc>
void ShortestDistance(const Fst<Arc> &fst, vector<typename Arc::Weight> *distance, bool reverse = false);
|
[bad link?] |
fstshortestdistance [--opts] a.fst [distance.txt]
--reverse: type = bool, default = false
Perform in the reverse direction
|
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
--
CyrilAllauzen - 05 Jul 2007