A new algorithm is presented for the search of the N-best paths in weighted graphs applied to the computation of the N-Best Sentence Hypotheses in Continuous Speech Recognition based on the One-Stage procedure. It is also shown how Beam Search techniques can be integrated in the algorithm leading to a very efficient sentence hypotheses enumeration algorithm
Keywords: N-Best Sentences, N Shortest Paths, Beam Search, Connected Word Recognition