We describe a lattice generation method that produces high-quality lattices with less than 10% increased computation over standard Viterbi decoding. Using the North American Business News (NAB) task, we show our method is within 0.2% in lattice word-error rate of full lattices, which are those that contain all the recognition hypotheses within the search beam. Our method is closely related to previous lattice generation methods, but applies to more general network topologies. We also give real-time results on the NAB task, in which we generate lattices in a first pass and then rescore them with stronger acoustic and language models in a second pass. We are able to achieve at 3x real-time a word error rate of 11.2% on the Eval 95 test set, which is only 1.7% worse than AT&Ts official bench-mark result that year using what was then a 1000x real-time system.