Abstract This paper presents an algorithm for calculating the stability of air flows in mine ventilation networks in case of random variations of air resistance. The analysis of the stability of air flows in the algorithm is based on two proposed criteria, which are calculated for each branch of mine ventilation network: the guaranteed minimum air flow and the relative deviation of the air flow. The algorithm calculates the distribution of both criteria in the mine ventilation network and allows detecting sections of the mine ventilation network with the least stable air flows. This information can be used to develop different measures to improve the stability of air flows in these sections, which is necessary to ensure the safety of mining operations. The advantages of the proposed algorithm are high calculating speed and intelligibility of the criteria for evaluating the airflow stability in each airway. The convergence of the algorithm is also studied in this paper for a set of ventilation networks. The results of numerical calculation of air flow stability for the undermining level of the Taimyrsky mine are presented.