扇形优化Dijkstra算法

• 作者: 张修如 胡树玮 赵洋
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: GIS 最短路径 扇形优化Dijkstra算法
• 年，卷（期）: 2006,（12）
• 所属期刊栏目: 智能、算法、软件工程
• 页码范围: 49-51,54
• 页数: 4页
• 分类号: TP301.6
• 字数: 2006字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2006.12.016

摘要

Dijkstra算法无数次遍历所有的临时标记结点,无疑成为该算法的一个瓶颈.在分析Dijkstra算法的基础上,结合平面网络的特点,从限制搜索范围和限定搜索方向两方面着手,在扇形区域内寻找最短路径,从而完成对Dijkstra算法的优化.优化算法基于有损算法,抛弃寻找最短路径时概率较小的顶点,直接寻求在方向和位置上趋向终点的顶点.它根据用户给出的起始顶点与目标顶点以及搜索的扇形角度查找最短路径.因此,在优化算法中,频繁遍历的顶点数量大幅度减少,提高了算法的速度和运行效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张修如	中南大学信息科学与工程学院	41	332	9.0	17.0
2	赵洋	中南大学交通运输工程学院	3	32	3.0	3.0
3	胡树玮	中南大学信息科学与工程学院	2	22	2.0	2.0