We use a variant of the DAG-SHORTEST-PATH algorithm . This algorithm finds shortest paths for uniformly weighted directed acyclic graphs. The first step of the algorithm is a topological sort of the vertices of the graph. It turns out that the state names of the word-graph that we obtain from the speech recogniser are already topologically sorted: state names are integers, and edges always connect to larger integers. The second step of the algorithm maintains an array A which records for each state vk the weight associated with the best path known from v0 to vk. A similar array, P, is used to represent for each state the history of this best path, as a sequence of QLFs (since that is what we want to obtain eventually).
The first step of the algorithm initialises these arrays such that
for each state
. For v0 we specify
. After this initialisation phase the algorithm
treats each edge of the graph in topologically sorted order of the
source vertex, as follows:
The function relax is defined on edges and updates the arrays if
a better path to a vertex has been found:
A simple generalisation of the algorithm has been implemented in order to obtain the N best solutions. In this case we maintain in the algorithm for each vertex the N best paths found so far. Such a generalisation increases the worst-case complexity by only a constant factor, and is very useful for development work.