Controlling the computational complexity to balance video quality and computation power consumption in motion estimation is a significant issue. This paper proposes a fast multi-path motion estimation algorithm for achieving computational complexity reduction as well as controllable computation. First, an enhanced interested diamond search pattern with search point reduction is proposed. In addition, the multi-path search concept is further combined in our proposal to search for the best matched block without suffering from the drawback of being trapped at the local minimum. Finally, by combining the adaptive threshold for early termination, the computation and coding performance can be adaptively controlled by our proposed algorithm to satisfy the various needs of video encoders. Experimental results show that the proposed algorithm with the ability of computation control can give better performance than the diamond search and its multi-path combined algorithm.