Shortest-distance algorithms

Shortest-distance algorithms are the workhorse for computations with finite-state automata. The “shortest distance” that these algorithms compute is, in general, the ⊕-sum of the labels of all paths from one state to another. To make computing this sum feasible, the labels on the arcs of the automaton must have certain properties. These properties man that the labels must be in a semiring. That explains that requirement.

Which semiring the labels are in determines what the computation does exactly. If the ⊕ operation chooses the minimum of the two values (like math::cost does), this computes the minimum-value path. If this value stands for a distance, this is actually the shortest distance, which explains the name of the algorithm. (In this case, the shortest distance also corresponds to a shortest path through the automaton.) However, depending on the semiring the ⊕-sum might be the overall probability, a weighted error, statistics for re-estimating parameters of a model, or something else.

There are various algorithms for computing shortest distances, which have different requirements on the topology and semirings, and have different characteristics. The most important distinction is whether they compute the sum over paths from one source state to all other states (single-source shortest-distance algorithms) or from all source states to all target states (all-pairs shortest-distance algorithms). Not all of these are currently implemented.

Single-source shortest distance

If the automaton is acyclic, the following algorithm can be used:

auto constexpr shortestDistanceAcyclic

Compute the shortest distance from source states to every other state in an acyclic automaton.

The result type is a lazy range with pairs (state, label).

The automaton must remain unchanged while the resulting range is being used.

This is only available in the forward direction if the label is a right semiring, and only available in the backward direction if the label is a left semiring.

The number of elements in the returned range, and the total time complexity, is \Theta(n) where n is the number of states in the automaton.

Space use depends on the properties of the automaton. Apart from the source states, weights are kept in memory only for states that have an arc from a state that has been emitted are kept in memory. As a state and its weight are emitted, it goes out of memory. However, traversal of the states uses topological order, which by default uses \Theta(n) space.

The automaton must have states() and arcsOnCompressed.

  • automaton -

    Pointer to the automaton to traverse. A copy of the pointer will be kept, and destructed when the range is destructed. The pointer must be copyable, and therefore cannot be a unique_ptr. The automaton should not change while the range is used.

  • initialStates -

    Range of pairs of (state, distance) giving the compressed initial labels to assign to states.

  • direction -

    The direction in which to traverse the automaton.

auto constexpr shortestDistanceAcyclicFrom

Compute the shortest distance from a single source state to every other state in an acyclic automaton.

  • automaton -

    The automaton to traverse.

  • initialState -

    The one initial state that will be assigned label math::one().

  • direction -

    The direction in which to traverse the automaton.

Table Of Contents

Previous topic

Examining automata

Next topic

Defining automata

This Page