最短路径问题设计论文

《最短路径问题设计论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录第1章绪论11.1问题描述11.2问题分析11.3相关标识（名词定义）11.4本文主要研究内容2第2章算法设计与实现32.1穷举法32.1.1穷举法描述32.1.2穷举法设计32.1.3穷举法分析62.2回溯法62.2.1回溯法描述62.2.2回溯法设计62.2.3回溯法分析92.3贪心法102.3.1贪心法描述102.3.2贪心法设计102.3.3贪心法分析112.4动态规划法112.4.1动态规划法描述112.4.2动态规划法设计122.4.3动态规划法分析12第3章实验结果分析与算法对比133.1输入数据133

2、.2实验结果与分析133.3算法分析与对比15第4章总结与展望16参考文献17第1章绪论1.1问题描述最短路径问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短，还可以引申到其它的度量，如时间、费用、线路容量等。最短路径算法的选择与实现是通道路线设计的基础，最短路径算法是计算机科学与地理信息科学等领域的研究热点，很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。本文

3、主要解决的问题是：给定带权有向图G＝(V,E)，对任意顶点,∈V（i≠j），求顶点到顶点的最短路径。即给定一个有向图，再给出任意2个不相邻的顶点，求2个顶点之间的最短距离。1.2问题分析给定一个带权有向图G＝(V,E)中的各个顶点之间的权值，对任意输入2个顶点,∈V（i≠j），求出从到的最短路径。输入：节点数目N，邻接矩阵VR[N][N]约束条件：其中，输出（目标函数）：min{Dist(,)}1.3相关标识（名词定义）（1）时间复杂度算法的时间复杂性是指执行算法所需要的时间。一般来说，计算机算法是问题规模n的函数f(n

4、)，算法的时间复杂性也因此记做T(n)=O(f(n))。因此，问题的规模n越大，算法执行时间的增长率与f(n)的增长率正相关，称作渐进时间复杂性。（2）空间复杂度空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间

5、的函数。（3）图的基本概念图：由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为：G=（V,E）。有向图：在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图。权：在图的边或弧中给出相关的数，称为权。权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。邻接矩阵：表示一个图的常用存储表示。它用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。1.4本文主要研究内容本文共分为4章，具体组织结构如下：第1章绪论。本章主要对最短距离问题进行描述和问题进行分

6、析，同时针对一些名词进行定义和解释。第2章算法的设计与实现。本章主要针对最短距离问题是用穷举法、回溯法、贪心法、动态规划法实现，并对算法进行描述、设计和分析。第3章实验结果分析与算法对比。本章主要对输入数据阐述，并对实验结果进行分析和算法分析与对比。第4章总结与展望。总结了本文的主要工作、重要贡献以及存在的不足，提出了进一步的工作内容，并对以后的研究工作进行了展望。第2章算法设计与实现2.1穷举法2.1.1穷举法描述穷举搜索（ExhaustiveSearchAlgorithm）法又称列举法，其基本思想是逐一列举问题所涉及

7、的所有情况。穷举法常用于解决“是否存在”或“有多少种可能”等问题。穷举法的算法特点是算法简单，但是运行时所花费的时间量大，需要将问题所涉及的有限种情形须一一列举，既不能重复，又不能遗漏。用穷举法实现广度优先搜索。广度优先搜索算法是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。2.1.2穷举法设计对问题使用广度优先遍历，将所有可能的结果首先保存起来

8、，再在结果中查找最短路径的结果，打印出来。其算法流程如图2.1所示，其算法步骤可以描述为如下：（1）从文件中读取图的节点数目、读取节点数目Npoint、起始点Start、结束点End、邻接矩阵**WeightArry。（2）动态分配存储空间MyMark[Npoint!]。（3）初始化路径存储状态为可更新状态和第0个路