摘要
在对地理信息系统中最短路径分析的实现方案和现有各种最短路径分析算法进行分析、研究的基础上 ,提出了“优化 Dijkstra算法”。该方法使 Dijkstra算法的搜索方向明显趋向于目标结点 ,减少了算法中遍历的结点数 ,从而提高了搜索速度。总结出两个 Dijkstra算法的优化途径 :对搜索到的临时标记结点按照最短路径值排序 ;减小结点的搜索范围即减少永久标记结点的数量。
New research and discovery on scheme of getting the best path in network and algorithms of shortest path are given by studying and analyzing other algorithms about shortest path. A new algorithm of shortest path analysis 'optimized Dijkstra algorithms' is given. This method makes the search direction of Dijkstra algorithm reach goal crunodes,reduce ransacking crunodes and improve searching speed.Optimizing measuresare proposed,shortening the temporary serch mark crunodes and reducing the node scope that is to reduce the number of permanent mark crunodes.
出处
《吉林大学学报（信息科学版）》
CAS
2002年第2期70-74,共5页
Journal of Jilin University（Information Science Edition）
