A Fast Algorithm for Quickest Path Reliability Evaluations in Multi-State Flow Networks

Many real-world multi-state systems can be modeled as multistate flow networks (MFN) such that the net flow into and out of a node (excluding the source and target nodes) is equal to zero, e.g., distribution systems and supply chains. The quickest path (QP) reliability problem is to evaluate the probability, i.e., R(d, t)-QP, that at least d units of data can be sent from the source node to the sink node through a single special minimal path (MP) within t units of time in an MFN. Such a special MP is called a (d, t)-QP here. In this study, a novel algorithm based on depth-first-search (DFS) is proposed to search for all (d, t)-QPs without solving two NP-hard problems: finding all minimal paths (MPs) in advance, and removing all infeasible (d, t)-QPs candidates. The correctness of the proposed Depth-First-Search (DFS)-based algorithm is proven, and an example is provided to illustrate the generation of all (d, t)-QPs. Furthermore, the analysis of the algorithm´s computational complexity and computer experiments indicate that it is more efficient than known algorithms.