# 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 void ShortestDistance(const Fst &fst, vector *distance, bool reverse = false); %DOX{namespacefst.html#ShortestDistance[]}% fstshortestdistance [--opts] a.fst [distance.txt] --reverse: type = bool, default = false Perform in the reverse direction

## Examples

(TropicalWeight)

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

## Caveats

See here for a discussion on efficient usage.

## References

-- CyrilAllauzen - 05 Jul 2007

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

This topic: FST > WebHome > FstQuickTour > ShortestDistanceDoc
Topic revision: r6 - 2012-05-13 - MichaelRiley

Copyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback