网络的K最短路算法研究

论文摘要

网络的最短路问题在现代计算机网络及交通系统中扮演着极其重要的角色,是最优化问题中的一个经典问题,它在实际生产生活中有着广泛的应用。在许多情况下,不仅仅要考虑最短路也要考虑次短路、次次短路,即K最短路。K最短路应用涉及很多领域,如通信、网络、交通工程、人工智能等。对该问题的研究不仅具有重要的理论意义,而且具有很大的实用价值。本文从图论的基本概念出发,对网络及其算法进行了深入的讨论和研究。从图论、最优化理论及蚁群算法等几个角度考虑这个问题,给出了基于相应的经典算法的高效、实用的K最短路算法,并给出了算法的时间复杂性分析。论文首先介绍了图及网络的基本概念、相关算法以及目前国内外的研究现状。对图论和网络的最短路经典的算法进行了详细的研究,详细地分析了Dijkstra、Floyd等算法,并总结各个算法的优点和不足。通过对最优化理论中的动态规划方法的详细分析,结合已有最短路算法,给出了基于动态规划方法的K最短路算法,形成了一套实现方便、运行高效的K最短路算法。对最小生成树的结构和Kruskal、Prim、广度优先搜索、深度优先搜索算法进行了深入分析,并总结各个算法的优点和不足。在求最小生成树算法的基础上,给出了基于最小生成树的K最短路算法,此算法具有高效和很强的实用性。最后,讨论了蚁群算法。蚁群算法是一种用于求解优化问题的新型模拟进化算法,该算法在许多相当困难的优化问题的求解中体现了极强的寻优能力和较好的性质。论文尝试着利用蚁群算法来解决网络最短路问题的算法,给出了相应的算法。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究目的及意义
• 1.2 国内外研究现状分析
• 1.3 本文主要研究内容
• 第2章 图与网络的基本概念及其算法
• 2.1 图的基本概念
• 2.2 树
• 2.3 图的表示形式
• 2.3.1 邻接矩阵
• 2.3.2 关联矩阵
• 2.3.3 可达矩阵
• 2.4 最短路径
• 2.5 DIJKSTRA 算法
• 2.5.1 Dijkstra 最短路算法
• 2.5.2 Dijkstra 算法分析
• 2.6 FLOYD 算法
• 2.6.1 Floyd 算法基本步骤
• 2.6.2 Floyd 算法复杂度分析
• 2.7 本章小结
• 第3章 基于动态规划法的K 最短路算法
• 3.1 动态规划方法
• 3.1.1 基本概念
• 3.1.2 基本思想
• 3.2 路径分叉
• 3.3 计算K 最短路算法
• 3.4 算法的复杂度
• 3.5 本章小结
• 第4章 基于树的K 最短路算法
• 4.1 最小树的形成
• 4.2 KRUSKAL 算法
• 4.3 PRIM 算法
• 4.4 广度优先搜索算法
• 4.5 深度优先搜索
• 4.6 K 最短路识别方案
• 4.7 K 最短路算法
• 4.8 算法分析
• 4.9 本章小结
• 第5章 基于蚁群算法的最短路算法算法
• 5.1 蚁群算法概述
• 5.2 蚁群算法的基本原理
• 5.3 基本蚁群算法数学模型
• 5.4 用基本蚁群算法求解最短路问题
• 5.5 蚁群算法分析
• 5.6 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢