Enumeration of all simple paths in a directed graph using Petri net: A systematic approach

The determination of all simple (or success) paths between two specified nodes in a directed graph finds various applications in graph theory, reliability evaluation of a system, etc. Many attempts at the problem of determining the S-T paths (simple or success paths between specified nodes S and T) have appeared in the literature [1–3]. The present paper, which utilizes the concept of the Petri net (PN), is yet another attempt at the same problem. The proposed technique is simple and tackles the problem in a systematic way. It is amenable to computer implementation.