Abstract: In multimedia network the routing problem is subject to QoS constraints. These problems are NP complete. BG heuristic algorithm can find sub optimal paths with one QoS constraint. In this paper improved multi lable algorithms are proposed, which combine the BG algorithm with the multi label algorithm. By reducing the search region of the multi label algorithm, these algorithms can lower the complexity of multi label algorithms.