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., 1 ⊕ *x* ⊕ *x* ^{2} ⊕ ... ⊕ *x* ^{ k +1} = 1 ⊕ *x* ⊕ *x* ^{2} ⊕ ... ⊕ *x* ^{ k }) (valid for non-negative `TropicalWeight`

) or *k* -closed when restricted to the automaton (valid for `TropicalWeight`

with no negative weight cycles).

template<class Arc> void ShortestDistance(const Fst<Arc> &fst, vector<typename Arc::Weight> *distance, bool reverse = false); |

fstshortestdistance [--opts] a.fst [distance.txt] --reverse: type = bool, default = false Perform in the reverse direction |

`A`

, over the tropical semiring:

(TropicalWeight)

State | Distance |
---|---|

`0` |
`0` |

`1` |
`3` |

`2` |
`5` |

`3` |
`7` |

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

State | Distance |
---|---|

`0` |
`10` |

`1` |
`7` |

`2` |
`7` |

`3` |
`3` |

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

`ShortestDistance:`

- TIme:
- Acyclic:
*O(V + E)* - Cyclic:
- Tropical semiring:
*O(V log V + E)* - General: exponential

- Tropical semiring:

- Acyclic:
- Space:
*O(V)*

See here for a discussion on efficient usage.

- Mehryar Mohri. Semiring Framework and Algorithms for Shortest-Distance Problems,
*Journal of Automata, Languages and Combinatorics*, 7(3):321-350, 2002.

-- CyrilAllauzen - 05 Jul 2007

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: 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

Ideas, requests, problems regarding TWiki? Send feedback