Abstract: A new algorithm, MCPN is proposed to estimate the reliability of a stochastic flow network, based on Monte Carlo sampling and Petri net modeling and simulation. Monte Carlo method is used as the frame of this algorithm to simulate the randomness of the network. To the randomly taken network states, a Petri net simulation is applied to judge whether it is valid by calculating the maximum flow of the relevant weighted graph. Simulation results showed that the Petri net method is efficient to calculate the maximum flow of the weighted graph.