This paper considers a network topological optimization problem with a reliability constraint. Jan et al. have proposed an algorithm to find the optimal selection of edges in networks, with minimum cost, under all-terminal reliability is not less than a given level. We extend their algorithm in order to apply to network design problems where operative probabilities of edges are different. Moreover, we accomplish several improvements to speed up the algorithm and show the effectiveness of our algorithm by numerical experiments.