转向约束网络中的对偶最短路径树原理及其原型算法

为比较有无转向约束条件下最短路径特征及其搜索算法的异同点,基于对偶图理论证明了转向约束网络中从单个源点到所有弧的最短路径集构成其对偶网络的生成树,提出了对偶最短路径树(DSPT)概念,并利用其分析算法之间的关系。研究结果表明:转向约束下的现有求解方法包括弧标号算法、节点标号算法和对偶网络法都可以统一到DSPT算法框架内,而且与无转向约束的最短路径树(SPT)算法在路径搜索策略上是相同的;对于转向约束网络中的最短路径问题可建立一个DSPT原型算法,结合各种SPT标号技术能设计出更多的有效算法。

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.