In current networks, the applications require more and more quality of services. Hence, a routing algorithm has to satisfy several constraints such as delay, bandwidth or jitter. This is called multicriteria routing problem. Since the multicriteria routing is an NP-Hard problem, we propose heuristics that quickly compute paths that satisfy Quality of service (QoS) constraints between a source node and a destination node. Several solutions exist in the literature; SAMCRA (Self Adaptive Multiple Constraints Routing Algorithm) is one of the most efficient algorithms, that was proposed by Van Mieghem et al. in 2001. SAMCRA is an exact unicast multi-constrained algorithm, which may have a high combinatorial complexity. In our paper, we investigate the possibility to replace SAMCRA by an improved k shortest paths algorithm. The simulation results show that applying such an algorithm significantly reduces the computation time while giving satisfying solutions.