We present a decoder for dialogue systems having both automatic speech recognition (ASR) and natural language (NL) understanding. Accurate and fast decoding of spoken utterances is a key to speech understanding. A good set of multiple word hypotheses produced by a decoder is also crucial for flexible integration of knowledge sources for language understanding. We introduce three contributions to improve the search efficiency and the effectiveness of our decoder, namely: (1) handling of long-term language models with crossword triphone models, (2) speed-up of search and likelihood computation; and (3) construction of high quality word graphs for interfaces between the ASR and NL understanding modules. The search algorithm was successfully applied to a natural language call routing task in a banking domain. As a result, we achieve both, word hypothesis decoding and word graph generation in real time with nearly no loss in word error rate in speech recognition.