Abstract: The shortest path problem with complex constraints is described, and the application of deviation algorithm, a kind of k shortest paths algorithms, to this problem is introduced. The factors that affect the efficiency of the algorithm are analyzed, and an enhancement to the algorithm is proposed to improve the efficiency. Simulation results show that this enhancement is very efficient.