Principles and its prototype algorithm for dual shortest path tree in networks with turning constraints

To analyze the difference and similarity between the shortest path characteristics and searching algorithms with and without turning constraints, dual graph theory was studied, the spanning tree of dual network was constructed with the shortest path set from a source node to all arcs in turning constraint network, the concept of dual shortest path tree(DSPT) was put forward and used for algorithm comparison.Analysis result shows that the present solution methods with turning constraints, including arc-labeling algorithm, node-labeling algorithm and dual-network method, can be unified into the same DSPT algorithmic frame, and have the same path searching strategies as the shortest path tree(SPT) algorithm without turning constraints; a prototype DSPT algorithm can be developed for the shortest path problem in networks with turning constraints, and more efficient algorithms can be designed according to different SPT labeling techniques.