Block matching technique is the most significant tool in motion estimation and compensation in video compression. Block matching is either fixed size block matching (FSBM) techniques or variable size block matching (VSBM). Rate distortion optimization problem is related with it. The R-D optimization, NP hard problem, is solved using Lagrange’s parameter to find a constrained path, where a given PSNR (distortion) and bit rate is achieved. In this paper, we modify and study the A*Prune algorithm used in QoS routing in network ,to solve the R-D optimization problem of video compression .we cast the R-D optimization problem as KMCSP (K multiple constrained shortest path problem). The modification presented in this paper is applied to DVF and DFD both and are constrained simultaneously to find any optional number of constrained shortest paths.