Difference: ShortestDistanceDoc (1 vs. 9)

Revision 92018-06-18 - KyleGorman

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

ShortestDistance

Line: 62 to 62
 ShortestDistance:
  • TIme:
    • Acyclic: O(V + E)
Added:
>
>
    • Cyclic:
 
    • Tropical semiring: O(V log V + E)
Changed:
<
<
    • General: exponential
>
>
      • General: exponential
 
  • Space: O(V)
where V = # of states and E = # of arcs.

Revision 82018-04-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

ShortestDistance

Line: 16 to 16
 |
template<class Arc>
void ShortestDistance(const Fst<Arc> &fst, vector<typename Arc::Weight> *distance, bool reverse = false);
Changed:
<
<
| doc [bad link?] |
>
>
|
 |
fstshortestdistance [--opts] a.fst [distance.txt]
    --reverse: type = bool, default = false
      Perform in the reverse direction
Changed:
<
<
||
>
>
|
 

Examples

Revision 72014-04-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

ShortestDistance

Line: 71 to 71
  See here for a discussion on efficient usage.
Added:
>
>

See Also

ShortestPath, State Queues

 

References

Revision 62012-05-13 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

ShortestDistance

Line: 67 to 67
 
  • Space: O(V)
where V = # of states and E = # of arcs.
Added:
>
>

Caveats

See here for a discussion on efficient usage.

 

References

Revision 52011-12-06 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

ShortestDistance

Line: 29 to 29
  shortestdistance.jpg
Added:
>
>
(TropicalWeight)
 

Shortest distance from the initial state

State Distance

Revision 42007-07-11 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

ShortestDistance

Line: 9 to 9
 ⊕-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)

Changed:
<
<
and k -closed (i.e., 1xx 2 ⊕ ... ⊕ x k +1 = 1xx 2 ⊕ ... ⊕ x k ).
>
>
and k -closed (i.e., 1xx 2 ⊕ ... ⊕ x k +1 = 1xx 2 ⊕ ... ⊕ x k ) (valid for TropicalWeight).
 

Usage

Revision 32007-07-09 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

ShortestDistance

Line: 23 to 23
  Perform in the reverse direction ||
Added:
>
>

Examples

A, over the tropical semiring:

shortestdistance.jpg

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:

Line: 41 to 73
 

-- CyrilAllauzen - 05 Jul 2007 \ No newline at end of file

Added:
>
>
META FILEATTACHMENT attachment="shortestdistance.jpg" attr="" comment="Shortest distance input example" date="1184013116" name="shortestdistance.jpg" path="shortestdistance.jpg" size="9583" stream="shortestdistance.jpg" user="Main.CyrilAllauzen" version="1"

Revision 22007-07-05 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

ShortestDistance

Line: 9 to 9
 ⊕-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)

Changed:
<
<
and k -closed (i.e., 1 ⊕ xx 2 ⊕ ... ⊕ x k +1 = 1 ⊕ xx 2 ⊕ ... ⊕ x k ).
>
>
and k -closed (i.e., 1xx 2 ⊕ ... ⊕ x k +1 = 1xx 2 ⊕ ... ⊕ x k ).
 

Usage

Revision 12007-07-05 - CyrilAllauzen

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="FstQuickTour"

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., 1 ⊕ xx 2 ⊕ ... ⊕ x k +1 = 1 ⊕ xx 2 ⊕ ... ⊕ x k ).

Usage

template<class Arc>
void ShortestDistance(const Fst<Arc> &fst, vector<typename Arc::Weight> *distance, bool reverse = false);
doc [bad link?]
fstshortestdistance [--opts] a.fst [distance.txt]
    --reverse: type = bool, default = false
      Perform in the reverse direction

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

 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback