A dictionary algorithm for the solution to the generalized quickest path reliability problem

Many real-world systems, such as computer and communication networks, transportation networks, social networks, power transmission and distribution systems, and others, can be modeled as multi-state flow networks. The generalized quickest path reliability problem (GQPRP) concerns the evaluation of the network reliability at level ( d, T, b ) defined as the probability of transmitting d units of flow from a source node to a destination node through a single minimal path within a time of T and a budget limit of b , under more general assumptions than in the QPRP: link capacities may be positive non-integers, and component reliabilities in one link can be correlated. All existing methods solve the problem by assessing network reliability for a given transmission time. In this paper, we present a very efficient algorithm that, given a flow network, a given flow, and a budget constraint, allows us to determine all attainable transmission times T and corresponding to them all ( d, T, b )-MPs. The proposed algorithm uses a dictionary as a fundamental data structure. It is based on the observation that for T ′ > T , some of ( d, T, b )-MPs can also be ( d, T ′, b )-MPs and it also effectively indicates what ( d, T, b )-MPs are ( d, T ′, b )-MPs. Its correctness and computational complexity are proven. All multitudinous numerical examples demonstrate that the proposed approach is much more efficient than other competitive methods. Moreover, the presented algorithm can work under the aforementioned more general assumptions.