Abstract: In order to compute the multi-state two-terminal reliability, a multi-valued discrete probability model MDD_WS2TR is defined. MFMC_MDD algorithm based on max-flow min-cut theorem is proposed, which combines the edges in the minimal cuts without considering the insignificant edge in the dense network. Especially, in the process of building MDD of the network, the operator TBoolean is defined to prune the MDD. Then the state space is compressed and the complexity of merging MDD is reduced. Finally MFMC_MDD algorithm is tested on a group of stochastic flow networks. The experimental results show that the proposed algorithm is effective.