A modified Viterbi scoring procedure is presented in this paper based on Dijkstra's shortest-path algorithm. In HMM-based speech recognition systems, the Viterbi scoring plays a significant role in finding the best matching model, but its computational complexity is linearly proportional to the number of reference models and their states. Therefore, the complexity is serious in implementing a high-speed speech recognition system. In the proposed method, the Viterbi scoring is translated into the searching of a minimum path, and the shortest-path algorithm is exploited to decrease the computational complexity while preventing the recognition accuracy from deteriorating. In addition, a two-phase comparison structure is proposed to manage state probabilities efficiently. Simulation results show that the proposed method saves computational complexity and recognition time by more than 21% and 10% compared to the conventional Viterbi scoring and the previous early termination, respectively. The improvement of the proposed method becomes significant as the numbers of reference models, states, and Gaussian mixture models increase, which means that the proposed method is more desirable for recent speech recognition systems that deals with complex models.