[1]胡树玮 张修如 赵洋.扇形优化Dijkstra算法[J].计算机技术与发展,2006,(12):49-51.
　HU Shu-wei,ZHANG Xiu-ru,ZHAO Yang.Sector Optimization Dijkstra Algorithm[J].,2006,(12):49-51.
点击复制

扇形优化Dijkstra算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2006年12期
页码:
49-51
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
Sector Optimization Dijkstra Algorithm
文章编号:
1673-629X（2006）12-0049-03
作者:
胡树玮1 张修如1 赵洋2
[1]中南大学信息科学与工程学院[2]中南大学交通运输工程学院
Author(s):
HU Shu-wei;  ZHANG Xiu-ru;  ZHAO Yang
[1]School of Information Science ＆ Engineering, Central South University[2]School of Traffic ＆ Transportation Engineering,Central South University
关键词:
GIS; 最短路径; 扇形优化Dijkstra算法
Keywords:
GIS;  shortest path; sector optimization Dijkstra algorithm
分类号:
TP301.6
文献标志码:
A
摘要:
Dijkstra算法无数次遍历所有的临时标记结点，无疑成为该算法的一个瓶颈。在分析Dijkstra算法的基础上，结合平面网络的特点，从限制搜索范围和限定搜索方向两方面着手，在扇形区域内寻找最短路径，从而完成对Dijkstra算法的优化。优化算法基于有损算法，抛弃寻找最短路径时概率较小的顶点，直接寻求在方向和位置上趋向终点的顶点。它根据用户给出的起始顶点与目标顶点以及搜索的扇形角度查找最短路径。因此，在优化算法中，频繁遍历的顶点数量大幅度减少，提高了算法的速度和运行效率
Abstract:
All temporary marked nodes are searched many times in Dijkstra algorithm. It becomes bottleneck obviously. An optimization algorithm is presented in this paper baaed on the analysis of Dijkstra＇s algorithm. It searches the shortest path within the sector limit because searching area and searching direction are limited. In the course of the optimization algorithm running, these nodes away from the shortest path are abandoned and those nodes close to goal from direction or position are processed. It finds a shortest path according to start node, goal node and angle of searching sector given by user. So the number of processed nodes is largely reduced in the optimization algorithm. Speed and efficiency of the optimizaton algorithm are improved

相似文献/References:

[1]卢照 师军 于海蛟 方昕.城市路网的最短路径并行求解[J].计算机技术与发展,2010,(01):78.
　LU Zhao,SHI Jun,YU Hai-jiao,et al.Solving the Shortest Path in Parallel of City Road Network[J].,2010,(12):78.
[2]宋世杰 刘高峰 周忠友 卢小亮.基于改进蚁群算法求解最短路径和TSP问题[J].计算机技术与发展,2010,(04):144.
　SONG Shi-jie,LIU Gao-feng,ZHOU Zhong-you,et al.An Improved Ant Colony Algorithm Solving the Shortest Path and TSP Problem[J].,2010,(12):144.
[3]李丽娟 石奋苏.基于ComGIS的生态环境状况查询及统计分析系统[J].计算机技术与发展,2009,(05):245.
　LI Li-juan,SHI Fen-su.Research of Query and Statistical Analysis System for Ecological Environment Based on ComGIS[J].,2009,(12):245.
[4]赵亚萍.基于Visual C#．NET的空间缓冲区分析开发[J].计算机技术与发展,2009,(12):29.
　ZHAO Ya-ping.Spatial Buffer Analysis Development Based on Visual C#. NET[J].,2009,(12):29.
[5]李培 何中市.基于ArcGIS和GPS的水电气管理系统设计与实现[J].计算机技术与发展,2009,(01):172.
　LI Pei,HE Zhong-shi.Design and Implementation Water, Electricity and Gas Management System Based on ArcGIS and GPS[J].,2009,(12):172.
[6]刘为峰 徐造林 黄永葛.基于RS、GIS集成的水深探测研究[J].计算机技术与发展,2008,(02):240.
　LIU Wei-feng,XU Zao-lin,HUANG Yong-ge.Water Depth Detection Study Based on Integration of RS and GIS[J].,2008,(12):240.
[7]孙芹芹 陈少沛[] 谭建军.基于MDA的城市地质防灾应急GIS模型研究[J].计算机技术与发展,2008,(07):184.
　SUN Qin-qin,CHEN Shao-pei,TAN Jian-jun.Study on MDA Model of Urban Geologic Hazard Preparedness GIS[J].,2008,(12):184.
[8]袁伟 洪玫 魏冬梅.基于B／S模式的WebGIS设计与实现[J].计算机技术与发展,2008,(08):8.
　YUAN Wei,HONG Mei,WEI Dong-mei.WebGIS Design and Implementation Based on B/S Mode[J].,2008,(12):8.
[9]聂跃光 陈立潮 陈湖.基于密度的空间聚类算法研究[J].计算机技术与发展,2008,(08):91.
　NIE Yue-guang,CHEN Li-chao,CHEN Hu.Research of Spatial Clustering Algorithms Based on Density[J].,2008,(12):91.
[10]芦东昕 李典蔚 柳长安.基于AJAX和Servlet的Web GIS的研究与实现[J].计算机技术与发展,2007,(03):193.
　LU Dong-xin,LI Dian-wei,LIU Chang-an.Research ＆ Implementation of Web GIS Based on AJAX and Servlet[J].,2007,(12):193.

备注/Memo

备注/Memo:
胡树玮（1978-），女，山东济宁人．硕士研究生，研究方向为面向对象程序分析设计、最短路径在物流方面的应用；张修如，副教授，研究方向为面向对象程序分析设计、物流
更新日期/Last Update: 1900-01-01