[4/19/2014] After a recent upgrade, we have been having problems with runaway TWiki processes that cause this server to eventually freeze. We are working on it.

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

).

`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)* - Tropical semiring:
*O(V log V + E)* - General:
*exponential*

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

Topic revision: r6 - 2012-05-13 - MichaelRiley

Copyright © 2008-2014 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