A Simple Universal Generating Function Method to Search for All Minimal Paths in Networks

Evaluating network reliability is an important topic in planning, designing, and control of systems, and the minimal-path (MP) set is one of the fundamental tools for evaluating network reliability. A straightforward and simple algorithm is presented here for finding all MPs before calculating the binary-state network reliability between the source node and the sink node (i.e., one-to-one reliability). It is based on the universal generating function method (UGFM) and a generalized composition operator. The computational complexity of the proposed algorithm is also analyzed. Finally, an example is given to illustrate how all MPs are generated using the proposed UGFM.