Several challenging issues exist in quality-of-service (QoS) provisioning in networks, and the QoS constrained routing is one of the most important issues. The QoS routing from a source to a destination leads to the well known multi-constrained path problem (MCP). The objective of MCP is to find a feasible path with respect to a set of QoS constraints. Since this problem is NP-complete, the solutions proposed in the literature are either time-consuming, or do not guarantee to find a solution even if the problem is feasible. Some of the most efficient algorithms proposed by Kuipers and al. are SAMCRA (exact resolution) and TAMCRA (heuristic). Based on the same ideas (using a Dijkstra-like search with a non-linear function and a reduction of the space search by non-dominance principle), we propose an exact algorithm, that manipulates the constraints to improve significantly the computation time. For hard instances, the results are similar to SAMCRA, but for easier instances, reinforcing the constraints leads to reduce the space search with a high probability of finding a solution. In some cases the algorithm memorized 40% less non-dominated paths than SAMCRA. We then show how, in specific cases, the solution can be improved by using a more flexible structure than paths.