# 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., 1xx 2 ⊕ ... ⊕ x k +1 = 1xx 2 ⊕ ... ⊕ x k ) (valid for non-negative `TropicalWeight`) or k -closed when restricted to the automaton (valid for `TropicalWeight` with no negative weight cycles).

## Usage

 ```template void ShortestDistance(const Fst &fst, vector *distance, bool reverse = false); ``` ```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)
• Cyclic:
• 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
Edit | Watch | Print version | History: r10 < r9 < r8 < r7 < r6 | Backlinks | Raw View | More topic actions
Topic revision: r10 - 2019-11-05 - 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