TWiki> FST Web>FstQuickTour>ShortestDistanceDoc (2019-11-05, MichaelRiley)

# 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

### `A`, over the tropical semiring: (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. jpg shortestdistance.jpg r1 manage 9.4 K 2007-07-09 - 20:31 CyrilAllauzen Shortest distance input example