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., 1xx 2 ⊕ ... ⊕ x k +1 = 1xx 2 ⊕ ... ⊕ x k ) (valid for TropicalWeight).

Usage

template<class Arc>
void ShortestDistance(const Fst<Arc> &fst, vector<typename Arc::Weight> *distance, bool reverse = false);
doc [bad link?]
fstshortestdistance [--opts] a.fst [distance.txt]
    --reverse: type = bool, default = false
      Perform in the reverse direction

Examples

A, over the tropical semiring:

shortestdistance.jpg

Shortest distance from the initial state

State Distance
0 0
1 3
2 5
3 7

ShortestDistance(A, &distance);
fstshortestdistance a.fst

Shortest distance to the final states

State Distance
0 10
1 7
2 7
3 3

ShortestDistance(A, &distance, true);
fstshortestdistance --reverse A.fst

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

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg shortestdistance.jpg r1 manage 9.4 K 2007-07-09 - 20:31 UnknownUser Shortest distance input example
Edit | Attach | Watch | Print version | History: r9 | r6 < r5 < r4 < r3 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r4 - 2007-07-11 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback