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

## 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
Edit | Attach | Watch | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r5 - 2011-12-06 - 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