中文核心期刊
CSCD来源期刊
中国科技核心期刊
RCCSE中国核心学术期刊

重庆交通大学学报(自然科学版) ›› 2015, Vol. 34 ›› Issue (3): 93-98.DOI: 10.3969/j.issn.1674-0696.2015.03.20

• • 上一篇    下一篇

基于深度优先反向搜索算法确定有效路径集合

张建旭,蒋燕, 刘兴国   

  1. 重庆交通大学 交通运输学院,重庆 400074
  • 收稿日期:2013-12-11 修回日期:2014-02-22 出版日期:2015-06-20 发布日期:2015-07-07
  • 作者简介:张建旭(1978-),男,河南许昌人,副教授,博士,主要从事综合交通规划与管理方面的研究。E-mail:jexu@qq.com。
  • 基金资助:
    国家自然科学基金项目(51308569)

Determining Effective Paths Set Based on Reverse Depth-First Search Algorithm

Zhang Jianxu, Jiang Yan, Liu Xingguo   

  1. School of Traffic & Transportation, Chongqing Jiaotong University, Chongqing 400074, China
  • Received:2013-12-11 Revised:2014-02-22 Online:2015-06-20 Published:2015-07-07

摘要: 基于最短路径中任意路段因发生交通事件而失效时的替代路径搜索,合理界定了有效路径的阻抗值范围。参考深度优先算法和有效路径Dail算法离终点越来越近的思想,提出了一种从终点出发,反向搜索前置节点的多条有效路径搜索算法。算例结果表明:该算法能自动识别与路网结构相关的有效路径阻抗值范围,且能快速找到阻抗范围内的有效路径集合。

关键词: 交通工程, 图论, 有效路径, 深度优先算法, Floyd算法

Abstract: Based on the definition of alternative path, the range of effective path impedance values was identified. Adopting the depth-first algorithm and the idea of getting closer to the end from the effective path Dail algorithm, an effective paths search algorithm which starts from the end node to the front node was proposed. Numerical results show that, the effective path search algorithm not only identifies the impedance values range associated with the network structure automatically, but also finds the effective path sets quickly.

Key words: traffic engineering, graph theory, effective path, depth-first search algorithm, Floyd algorithm

中图分类号: