Shortest Path Algorithms For Petri Nets

Abstract

Petri net is a mathematical and graphical tool for modeling and analysing discrete event systems. This paper focuses on a driving Petri net system from a given initial state to a desired state via minimum number of operations, that is, through the shortest transition sequence which is called as the shortest path problem. Thereby, two algorithms are developed to obtain the shortest path for Petri nets. The first algorithm, namely Forward Algorithm, uses integer programming approach and makes the process start from the initial state towards the desired state. The second algorithm, namely Backward Algorithm, uses most promising state to generate the shortest path and makes the process start from the desired state back to the initial state. Proposed algorithms do not deal with the reachability tree or graph of the net under analysis and use memory only for storing the obtained paths unlike the approaches based on the reachability tree. Moreover, the algorithms can be applied to general Petri nets without any restriction. Simulation results demonstrate that the proposed algorithms reduces the computational time and complexity significantly.