网络最短路径定界搜索算法

• 作者: 李引珍 郭耀煌
• 来源期刊: 西南交通大学学报
• 学科: 交通运输
• 关键词: 网络分析 最短路径 双向定界搜索算法 效率
• 年，卷（期）: 2004,（5）
• 页码范围: 561-564
• 页数: 4页
• 分类号: U113
• 字数: 3580字
• 语种: 中文
• DOI: 10.3969/j.issn.0258-2724.2004.05.001

摘要

用Dijkstra算法求解大规模网络两顶点间最短路径时,需计算大量与最短路径无关的顶点,效率较低.双向定界搜索算法是首先对网络进行双向搜索,得到一条经任意点的最短路径.一般情况下,这条路径已非常接近、甚至等于最短路径.然后,以此路径的标号(即路径长)作为搜索计算的界,进行双向标号计算,对超过界的顶点不再计算,以提高计算效率.算法分析表明,用该算法可使计算效率提高约一倍.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郭耀煌	西南交通大学经济管理学院	144	4757	34.0	65.0
2	李引珍	西南交通大学经济管理学院	102	793	16.0	20.0