菜单
　　
    摘  要：计算最短路径的经典算法之一就是Dijkstra算法，它是解决工程中最短路径问题的基础。但是，传统的Dijkstra算法在求解节点间最短路径时，对已标识节点外的大量节点进行了计算，从而影响了算法的速度。本毕业论文在传统Dijkstra算法的基础上，对最短路径上节点的邻节点做了一些处理，从而不涉及到其他的一些节点。故而，此优化算法在计算的节点数较传统算法大幅减少，提高了算法的速度。本文通过实际应用对改进后的算法进行了简单的验证。7025
    关键词：最短路径；Dijkstra算法；优化算法

    Optimization and Application of Dijkstra Algorithm for
     the Shortest Path
    Abstract：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, Therefore,the number of processed nodes is largely reduced in the optimization algorithm,and efficiency of the optimization algorithm is improved.
    Key Words：the shortest path; Dijkstra algorithm; optimization algorithm
    目    录

    摘  要    1
    引言    1
    1.绪论    2
    1.1 最短路径算法的研究现状    2
    1.2 最短路径算法的研究意义    2
    1.3 已有Dijkstra算法存在的问题    2
    2.经典的Dijkstra算法    3
    2.1 Dijkstra算法的思想    3
    2.2 Dijkstra算法的步骤    4
    3.优化的Dijkstra算法    6
    3.1 两种Dijkstra优化算法    6
    3.2 优化的Dijkstra算法    6
    4.Dijkstra算法的应用    7
    4.1 Dijkstra算法在城市建设选址中的应用    7
    4.2 Dijkstra算法在医院间的应用    8
    4.3 Dijkstra算法在交通系统中的应用    9
    5.总结    10
    参考文献    11
    致谢    12
    最短路径算法中Dijkstra算法的优化及应用引言
    最短路径问题是图论中的一个重要问题, 在交通运输、物流配送、网络分析等方面都有着广泛的应用,求解最短路径的方法也有很多, 诸如动态规划法、启发式算法、迭代法等, 本文就经典的Dijkstra算法进行分析, 提出一种改进的算法,并对改进算法进行算法分析。
    1.绪论
    1.1最短路径算法的研究现状
    最短路径在20世纪初开始受到人们的重视，关于它的求解方法，当时有很多科学家在研究。但给出求解的基本思想的人直到1959年才出现，是一位名叫Edsger Wybe Dijkstra (迪杰斯特拉)的荷兰计算机科学家，他不仅给出了求解的基本思想，还给出了算法。他给出的算法主要解决的问题是从某一个固定的点到其他各点的最短路径问题。后来这个算法被誉为一代经典，被称作Dijkstra算法。后来，人们逐渐从两个方面来研究最短路径，分为完全信息情况下和不确定情况下。确定情况下对最短路径的研究的过程中，发展出了很多高效的算法，其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyfus算法已成为确定情况下的经典算法。而不确定情况下对最短问题的研究又分成了四个方面：研究路段长度随机变化的最短路径问题，以Frank和Mirchandani为代表；研究不同费用函数最短路径问题，以Loui、Muethy和Sarkar为代表；研究时间独立情况下的路段长度随机变化的最短路径问题，Hall、LiPing Fu、Lett.R.Ril、Elise和Hani为代表；研究路段长度为区间范围的最短路径问题，以Tomas和Rajeev为代表。其中，当目标是期望最短路径时,问题转化为将边的权重用期望值表示的最短路径问题。
  1. 上一篇：ASP.net宿舍管理系统的设计与实现+ER图
  2. 下一篇：ASP.net在线学习辅导系统的设计与实现

  1. 基于MATLAB的图像增强算法设计

  2. 基于Kinect的手势跟踪与识别算法设计

  3. JAVA+MYSQL《算法与数据结构...

  4. 神经网络算法在核素识别中的应用研究

  5. 人脸图像品质评估算法设计与实现

  6. 基于RGB-D摄像机的图像分割算法研究与实现

  7. 云虚拟环境下资源分配优化算法的研究

  8. java+mysql车辆管理系统的设计+源代码

  9. 河岸冲刷和泥沙淤积的监测国内外研究现状

  10. 大众媒体对公共政策制定的影响

  11. 酸性水汽提装置总汽提塔设计+CAD图纸

  12. 杂拟谷盗体内共生菌沃尔...

  13. 乳业同业并购式全产业链...

  14. 当代大学生慈善意识研究+文献综述

  15. 中考体育项目与体育教学合理结合的研究

  16. 电站锅炉暖风器设计任务书

  17. 十二层带中心支撑钢结构...

　　

About

751论文网手机版...

主页：http://www.751com.cn

关闭返回