| 转向约束网络中的对偶最短路径树原理及其原型算法 |
| |
| 引用本文： | 任刚, 王炜. 转向约束网络中的对偶最短路径树原理及其原型算法[J]. 交通运输工程学报, 2008, 8(4): 84-89. |
| |
| 作者姓名： | 任刚 王炜 |
| |
| 作者单位： | 东南大学 江苏省交通规划与管理重点实验室,江苏 南京 210096 |
| |
| 基金项目： | 国家重点基础研究发展计划(973计划),国家自然科学基金,教育部高等学校博士学科点专项科研基金 |
| |
| 摘 要： | 
为比较有无转向约束条件下最短路径特征及其搜索算法的异同点, 基于对偶图理论证明了转向约束网络中从单个源点到所有弧的最短路径集构成其对偶网络的生成树, 提出了对偶最短路径树(DSPT)概念, 并利用其分析算法之间的关系。
研究结果表明: 转向约束下的现有求解方法包括弧标号算法、节点标号算法和对偶网络法都可以统一到DSPT算法框架内, 而且与无转向约束的最短路径树(SPT)算法在路径搜索策略上是相同的; 对于转向约束网络中的最短路径问题可建立一个DSPT原型算法, 结合各种SPT标号技术能设计出更多的有效算法。
|
| 关 键 词： | 交通网络 对偶最短路径树 对偶图 转向约束 原型算法 |
| 收稿时间： | 2008-01-05 |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《交通运输工程学报》浏览原始摘要信息 |
|
点击此处可从《交通运输工程学报》下载全文 |
|
