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

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

作　　者：任刚[1] 王炜[1] 

机构地区：[1]东南大学江苏省交通规划与管理重点实验室,江苏南京210096

出　　处：《交通运输工程学报》2008年第4期84-89,共6页Journal of Traffic and Transportation Engineering

基　　金：国家973计划项目(2006CB705500);国家自然科学基金项目(50608018);高等学校博士学科点专项科研基金项目(20070286006)

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

关 键 词：交通网络 对偶最短路径树 对偶图 转向约束 原型算法 

分 类 号：U491.13[交通运输工程—交通运输规划与管理]