  The single shortest path algorithm is undefined for weighted finite-state
automata over non-idempotent semirings because such semirings do not guarantee
the existence of a shortest path. However, in non-idempotent semirings
admitting an order satisfying a monotonicity condition (such as the plus-times
or log semirings), the notion of shortest string is well-defined. We describe
an algorithm which finds the shortest string for a weighted non-deterministic
automaton over such semirings using the backwards shortest distance of an
equivalent deterministic automaton (DFA) as a heuristic for A* search performed
over a companion idempotent semiring, which is proven to return the shortest
string. While there may be exponentially more states in the DFA, this algorithm
needs to visit only a small fraction of them if determinization is performed
"on the fly".

Formal Languages and Automata Theory;Computation and Language