Dijkstra最短路径算法的优化和改进.doc

本科毕业设计(论文)
Dijkstra最短路径算法的优化和改进
学生姓名:。
指导教师: 屹
专业、班级:信息
院(系):理
2013 年 6 月吉林
摘要
随着计算机和地理信息科学的发展,GIS(地理信息系统),,传统的Dijkstra算法在求解节点间最短路径时,对已标识节点外的大量节点进行了计算,从而影响了算法的速度.
该算法的主要特点是以起始点为中心向外层层扩展,,,对其进行了优化,此优化算法只对最短路径上节点的邻点做了一些处理,,仅仅涉及到节点的邻居集合及已标识集合中所有节点的邻居集合与已标识集合的差集,,此优化算法在计算的节点数较传统算法大幅减少,,这样就能使文章中算法的优化更为理想.
关键词最短路径;Dijkstra;优化算法
Abstract
With the development puter and geographic information science, the applications of GIS (Geographic Information System) are ing more and more widely. However, shortest path analysis is the key problem work analyses, Dijkstra algorithm is a classic arithmetic for the shortest path. It is the academic foundation that many engineerings were solved in the shortest path is use. When a shortest path between nodes is searched with Dijkstra algorithm, a lot of nodes away from lagged nodes are involved, so that the efficiency of Dijkstra algorithm is low.
Main features of the algorithm is the starting point as the center outward expansion layers until it extended to the end point. Dijkstra's algorithm is very representative of the shortest path algorithm, in many professional courses in the basic content as described in detail. The proposed algorithm updates the shortest path in the value of the minimum value of the shortest path to the node, only the set of neighbors of the node related to the identified set and a neighbor set of all nodes in the identified set with the set difference, its running time depends transfer the contact elements of the set of neighbors of quantity. essful search algorithm by reducing the search range and improved algorithm storage structure of these two main research directions to opt