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

本科毕业设计( 论文) Dijkstra 最短路径算法的优化和改进学生姓名:。指导教师: 屹专业、班级: 信息院(系):理 2013 年6月吉林摘要-I- 摘要随着计算机和地理信息科学的发展, GIS (地理信息系统)的应用领域越来越广. 最短路径分析是 GIS 地理网络分析功能中的一个关键性的问题. 计算最短路径的经典算法之一就是 Dijkstra 算法,,传统的 Dijkstra 算法在求解节点间最短路径时,对已标识节点外的大量节点进行了计算,从而影响了算法的速度. 该算法的主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止. Dijkstra 算法是很有代表性的最短路径算法, Dijkstra 算法的基础上, 对其进行了优化,此优化算法只对最短路径上节点的邻点做了一些处理,,仅仅涉及到节点的邻居集合及已标识集合中所有节点的邻居集合与已标识集合的差集,,此优化算法在计算的节点数较传统算法大幅减少,,这样就能使文章中算法的优化更为理想. 关键词最短路径; Dijkstra ;优化算法 Abstract - II- 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 isa 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 lotof 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 r