J.A. Bakker and J.H. ter Bekke (Netherlands)
Petri Net, recursive query, semantic model, shortest path,time complexity
This paper presents a recursive query language solution for the shortest path problem based on the transformation of a cyclic geometric graph into an acyclic time graph, i.e. an acyclic Petri Net specifying the possible transitions (turns) between successive rides on different roads. Using this transformation, the shortest path problem is transformed into a fastest tour problem. The time complexity of the proposed solution is O(N5 ), where N is the number of towns in the underlying geometry. The underlying algorithm guarantees termination.
Important Links:
Go Back
