Reference:

J. Desel and J. Esparza. Shortest paths in reachability graphs. Journal of Computer and System Sciences, 51(2):314–323, 1995.

Abstract:

We prove the following property for safe marked graphs, safe conflict-free Petri nets, and live and safe extended free-choice Petri nets: Given two markings , of the reachability graph, if some path leads from to , then some path of polynomial length in the number of transitions of the net leads from to .

Suggested BibTeX entry:

@article{DE95,
    author = {J. Desel and J. Esparza},
    journal = {Journal of Computer and System Sciences},
    number = {2},
    pages = {314--323},
    title = {Shortest Paths in Reachability Graphs},
    volume = {51},
    year = {1995}
}