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

本科毕业设计（论文）
Dijkstra最短路径算法的优化和改进
随着计算机和地理信息科学的发展，GIS （地理信息系统）的应用领域越来 短路径的经典算法之一就是i. Theiefoiejlie number of processed nodes is largely reduced m the optimization algontlun, and efficiency of the optimization algoiitlun is unproved. The improved algontlun is proved to be conect and efficient by expeimients and practical application. After some of the algontlun and the combmation of practical examples, so you can make the ailicle more ideal algontlun optimization.
Keywords The shortest path； Dijkstra； Optimization algontlun
目 录
方^ . ................................................................................................................................I
Abstract II
U .............................................................................................................................. Ill
第1章 绪论 1
国内外最短路径算法的发展及其概况 1
传统Dijkstra算法仍然存在的一些问题 1
本文工作 2
第2章 Dijkstra经典算法 3
引言 3
原理及应用 3
原理 3
应用 5
Dijkstia算法与其他主流算法的比较 6
搜索速度比较 6
搜索成功率比较 7
Dijkstra算法的优缺点 8
第3章 两点间最短路的改进的Dijkstra算法及其MATLAB实现 9
Dijkstia 矩阵算法 1 9
Dijkstia 矩阵算法 II 9
第4章 基于Dijkstia算法的优化算法的研究 13
几种优化算法 13
减小算法中成功搜索的搜索范围 13
改进算法的存储结构 13
本文对Dijlstra优化算法研究 14
优化目标 14
优化思路 14
-in-
问题描述 15
算法特点 19
优化和改进的结论 20
第5章 Dijkstia算法在物流上的应用 21
最优配送路线选择问题 22
改进的Dijkstra算法在最优配送路线确定中的实例 24
路径优化结果 26
结论 28
参考文献 29
致谢 30
附录 31
第1章绪论
最短路径算法是计算机科学与地理信息科学等领域研究的热点，其算法有很 多种，其中传统的Dijkstia算法一般用于计算一个源节点到所有其他节点的最小 代价路径，并且能够适应网络拓扑的变化，性能稳定，因而可以在运输路线规划 等领域都应用广泛》.
国内外最短路径算法的发展及其概况
最短路径在20世纪初开始受到人们的重视，关于它的求解方法，当时有很多 ，是一位名叫 Edsgei Wybe Dijkstia （迪杰斯特拉）的荷兰计算机科学家，他不仅给出了求解的 基本思想， ，被称作Dijkstia算 ，人们逐渐从两个方面来研究最短路径，分为完全信息情况下和不确定 ，发展出了很多高效的算法，其 中1958年的Bellman算法、1959年的Dijkstia算法、1969年的DieyfUs算法已成为确 ： 研究路段长度随机变化的最短路径问题，以Fiank和Muchandani为代表；研究不 同费用函数最短路径问题，以Loui、Muethy和Saikai为代表；研究时间独立情况 下的路段长度随机变化的最短路径问题，Hall、LiPmg Fu.