The A*Prune quality of service (QoS) routing algorithm was proposed to compute K-shortest paths satisfying multiple QoS constraints. The A*Prune is considered to be one of the practical routing algorithms for intelligent optical networks because of its flexibility in handling many practical constraints. This article gives detailed performance studies of the algorithm through extensive simulation experiments. We found that both the running time and the memory space requirements of the algorithm are large, especially when the network size increases. In this article, we also propose an approach to improving the performance of the A*Prune algorithm. The improvements should make the A*Prune algorithm more attractive for practical use in intelligent optical networks.