结合概率搜索定界的入度统计最短路径算法

• 作者: 敬明 邓卫
• 来源期刊: 交通运输系统工程与信息
• 学科: 交通运输
• 关键词: 交通工程 最短路算法 入度统计 概率搜索 无效顶点
• 年，卷（期）: 2011,（6）
• 所属期刊栏目: 系统工程理论与方法
• 页码范围: 169-174
• 分类号: U491.2
• 字数: 4952字
• 语种: 中文
• DOI: 10.3969/j.issn.1009-6744.2011.06.026

摘要

Dijkstra经典最短路径算法包括大量的排序运算,且需要对图中所有顶点进行计算,效率较低.本文针对有向网络,提出了与概率搜索定界结合的入度统计最短路径算法.该算法通过按概率搜索得到一条较短路径,依据路径长度和有向网络结构特征确定和顶点序号相关的节点阻抗最大值；采用入度统计算法代替经典的标号算法,在计算过程中根据节点阻抗最大值,采取一定方式剔除无效顶点(不在最短路径内的顶点),简化网络结构.本文提出的算法不需要进行排序运算,简化了运算过程,并且可以剔除大量的无效顶点,降低了网络复杂度.算例分析表明,相对于Dijkstra算法,结合概率搜索定界的入度统计算法大幅度提高了运算效率,具有实用性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邓卫	东南大学交通学院	157	3214	32.0	49.0
2	敬明	东南大学交通学院	5	67	4.0	5.0