The Minimum Cut Problem （MCP） is a classic NP （Nondeterministic Polynomial） -hard problem with broad applications in image segmentation and network reliability analysis. Warning Propagation （WP） algorithm， a factor graph-based inference method， has shown good scalability and structural adaptability when solving combinatorial optimization problems. However， its effectiveness on MCP is limited by path selection， factor graph construction， and convergence. Therefore， an Entropy-based Warning Propagation （EWP） algorithm was proposed to solve MCP. First， a Hidden Markov Model （HMM） -driven jump-point mechanism was introduced to select core propagation regions. At the same time， a batch-mapping factor graph transformation way was employed to reduce graph structural dimensionality effectively. Finally， a propagation freezing strategy that combined marginal probability and variable entropy was adopted to accelerate convergence. Experimental results demonstrate that EWP achieves good performance on graphs with different sizes， and especially has significant potential in large-scale graph optimization problems.