扇形优化Dijkstra算法

被引：6

作者：

胡树玮 ^{[1
]}

张修如 ^{[1
]}

赵洋 ^{[2
]}

机构：

[1] 中南大学信息科学与工程学院

[2] 中南大学交通运输工程学院

来源：

计算机技术与发展 | 2006年 / 12期

关键词：

GIS; 最短路径; 扇形优化Dijkstra算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：49 / 51+54 +54

页数：4