| 扇形优化Dijkstra算法 |
| |
| 引用本文： | 胡树玮,张修如,赵洋. 扇形优化Dijkstra算法[J]. 计算机技术与发展, 2006, 16(12): 49-52 |
| |
| 作者姓名： | 胡树玮 张修如 赵洋 |
| |
| 作者单位： | 1. 中南大学,信息科学与工程学院,湖南,长沙,410075
2. 中南大学,交通运输工程学院,湖南,长沙,410075 |
| |
| 摘 要： | Dijkstra算法无数次遍历所有的临时标记结点，无疑成为该算法的一个瓶颈。在分析Dijkstra算法的基础上，结合平面网络的特点，从限制搜索范围和限定搜索方向两方面着手，在扇形区域内寻找最短路径，从而完成对Dijkstra算法的优化。优化算法基于有损算法，抛弃寻找最短路径时概率较小的顶点，直接寻求在方向和位置上趋向终点的顶点。它根据用户给出的起始顶点与目标顶点以及搜索的扇形角度查找最短路径。因此，在优化算法中，频繁遍历的顶点数量大幅度减少，提高了算法的速度和运行效率。
|
| 关 键 词： | 最短路径 扇形优化Dijkstra算法 |
Sector Optimization Dijkstra Algorithm |
| |
| HU Shu-wei,ZHANG Xiu-ru,ZHAO Yang. Sector Optimization Dijkstra Algorithm[J]. Computer Technology and Development, 2006, 16(12): 49-52 |
| |
| Authors: | HU Shu-wei ZHANG Xiu-ru ZHAO Yang |
| |
| Abstract: | |
| |
| Keywords: | GIS |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
