To solve the problem of Quality-of-Service (QoS) routing in next generation high speed network,firstly a novel precomputation algorithm MKPPA for QoSR with accurate link-state information based on the K-optimal paths is proposed.Secondly a modified MKPPA,M_-MKPPA,is presented to adapt the inaccurate link-state information of the network by introducing an "alert point".Finally the theoretical analysis indicates that the MKPPA is not only fit to the QoSR in which all constraint parameters are additive but also the QoSR in which some constraint parameters are additive and the others are non-additive,the M_-MKPPA can adapt the dynamical character of link-state information of the network.The extensive simulation results show that the proposed algorithms have the higher routing computation success ratio with either accurate link-state information or inaccurate link-state information of the network.