基于Dijkstra的最短路径算法的优化及应用（毕业学术论文设计）.doc

第*章 具体章节标题 精品 本科学生毕业论文 论文题目： 基于Dijkstra的最短路径算法的优化及应用 学 院： 年 级： 专 业： 姓 名： 学 号： 指导教师： 2011年5月20日 精品 PAGE 摘要 随着计算机和地理信息科学的发展，GIS（地理信息系统）的应用领域越来越广。最短路径分析是GIS地理网络分析功能中的一个关键性的问题。计算最短路径的经典算法之一就是Dijkstra算法，许多工程中解决最短路径问题都是采用这种算法。然而，传统的Dijkstra算法在求解节点间最短路径时，对已标识节点外的大量节点进行了计算，从而影响了算法的速度。本文在传统Dijkstra算法的基础上，对其进行了优化，此优化算法只对最短路径上节点的邻居做了一些处理，从而不涉及到其他的一些节点。故而，此优化算法在计算的节点数较传统算法大幅减少，提高了算法的速度。本文通过实验和实际应用对改进后的算法进行了简单的验证。 关键词 最短路径；Dijkstra；优化算法 Abstract With the development of computer and geographic information science,the applications of GIS (Geographic Information System) are becoming more and more widely.However, shortest path analysis is the key problem of network 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.An optimization algorithm is presented in this paper based on analysis of Dijkstra algorithm.Only these nodes that the neighbor of nodes in the shortest path are processed,and other nodes are not processed.Therefore,the number of processed nodes is largely reduced in the optimization algorithm,and efficiency of the optimization algorithm is improved.The improved algorithm is proved to be correct and efficient by experiments and practical application. Key words the shortest path；Dijkstra；optimization algorithm 精品 目录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc294177728摘要 PAGEREF _Toc294177728 \h I HYPERLINK \l _Toc294177729Abstract PAGEREF _Toc294177729 \h II HYPERLINK \l _Toc294177730第一章 绪论 PAGEREF _Toc294177730 \h 1 HYPERLINK \l _Toc294177731一、国内外最短路径算法的发展及其概况 PAGEREF _Toc294177731 \h 1 HYPERLINK \l _Toc294177732二、传统Dijkstra算法仍然存在的一些问题 PAGEREF _Toc294177732 \h 1 HYPERLINK \l _Toc294177733三、本文研究的内容及意义 PAGEREF _Toc294177733 \h 2 HYPERLINK \l _Toc294177734第二章 Dijkstra经典算