Say we have a place-transition digraph system. A transition can fire if all input places have marks. A transition fires by consuming items from input places and placing one into each output place. A number near the transition is a transition price. So, for example, we can get an image like this: enter image description here

We want to find the cheapest path from From to To. So it is quite simple to see how one can modify Dijkstra to find a path in algorithm terms, yet in terms of formal theory in generalised case it does not look so simple and there can appear loops and loop step related conditions. So Is there a Dijkstra like pathfinding with condition satisfaction algorithm?

  • $\begingroup$ I think you should start with the case where all weights are 1 (this is hard enough for now) $\endgroup$
    – nir shahar
    May 29, 2020 at 9:29
  • $\begingroup$ What exactly is a "place-transition digraph system"? Can you give a self-contained definition? What's the difference between an item and a mark? What exactly are the semantics of a transition -- how many items does it consume? What counts as a path from one node to another? Are you asking about reachability in Petri nets? $\endgroup$
    – D.W.
    May 29, 2020 at 23:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.