Next Generation Internet applications provide guaranteed end-to-end Quality-of-Service (QoS). Optimization based on constraints for QoS routing is computationally complex and for this reason many heuristics have been proposed for routing in a practical situation. Among these Delay Constrained Least Cost (DCLC) routing is popular. In this paper we propose an algorithm for delay-constrained problems. Multimedia applications have stringent constraints on delay, delay-jitter, cost, etc. The main purpose of QoS routing is to find a feasible path that has sufficient resources to satisfy the constraints. The delay and cost constrained routing problem is NP-complete. This paper presents an technique called E-LARAC based on Lagrange Relaxation that gives a lower bound on the theoretical optimal solution. Simulation results show that it can obtain better performance than CBF and DCUR.