Optimal shortest path in reachability graph
Pascal Richard · 2003
We study the weighted shortest path problem in a Petri net reachability graph. Given two markings M and M: we want to find the weighted shortest firing sequence that leads from M to M'. We tackle this problem with a two step-procedure : first the optimal characteristic vector is computed, and then a sequence is built. We focus on state machines and live marked graphs. Efficient algorithms based on graph theory are presented to solve the first step. We also give a reachability result based on balanced firing sequences that are dominant for every marked graph. Finally we show that the problems solved at each step are separately NP-hard in the strong sense.