索过程，每向前走步可能访问批顶点，不像深度优先搜索那样会出现回退的现象。

因此它不是个递归的过程。

为了实现逐层访问，算法中使用了个队列以记忆正在访问的这层和上层的顶点，以便于向下层访问。

广度优先算法的主要代码如下取图的顶点个数定义访问标记数组访问顶点顶点作访问标记入队取图的顶点个数定义访问标记数组访问顶点顶点作访问标记,若顶点存在,重复检测的所有邻接顶点算法算法属于种启发式搜索算法，被广泛应用在最优路径求解和些策略设计的问题中。

所谓启发式搜索，与和这类盲目型搜索最大的不同，就在于当前搜索结点往下选择下步结点时，可以通过个启发函数来进行选择，选择代价最少的结点作为下步搜索结点而跳转其上遇到有个以上代价最少的结点，不妨选距离当前搜索点最近次展开的搜索点进行下步搜索。

个经过仔细设计的启发函数，往往在很快的时间内就可得到个搜索问题的最优解。

而算法最为核心的部分，就在于它的个估值函数的设计上其中是每个可能试探点的估值，它有两部分组成部分为，它表示从起始搜索点到当前点的代价通常用结点在搜索树中的深度来表示。

另部分，即，它表示启发式搜索中最为重要的部分，即当前结点到目标结点的估值。

算法保证找到最短路径最优解的条件，关键在于估价函数的选取估价值实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

估价值与实际值越接近，估价函数取得就越好。

算法的主要代码如下程序运行结果与分析图中各种算法的运行效果广度优先算法运行结果图广度优先搜索图是关于个节点进行广度优先搜索的运行结果，从节点开始，遍历与他相邻的节点,然后在遍历节点的相邻节点。

广度优先搜索算法中，解答图上结点的扩展是沿结点深度的断层进行，也就是说，结点的扩展是按它们接近起始结点的程度依次进行的。

首先生成第层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第层结点逐扩展，得到第二层结点，并检查第二层结点是否包含目标结点„„对长度为的任结点进行扩展之前，必须先考虑长度为的结点的每种可能的状态。

因此，对于同层结点来说，求解问题的价值是相同的，我们可以按任意顺序来扩展它们。

这里采用的原则是先生成的结点先扩展。

深度优先算法运行结果图深度优先搜索图是关于个节点进行深度优先搜索的运行结果，从节点开始，访问与他相邻的节点,然后再访问与节点相邻的节点，重复此过程直到找到目标节点为止。

深度优先搜索算法中，从起始结出发，访问它的任邻接结点再从出发，访问与邻接但还没有访问过的顶点然后再从出发，进行类似的访问„„如此进行下去，直至所有的邻接结点都被访问为止,如果此时还没有找到目标结点，则退回步，退到前次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。

如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问如果没有，就再退回步进行搜索。

重复上述过程，直到找到目标结点或图中所有顶点都被访问过为止。

对于多个邻接结点，求解问题的价值是相同的，因此我们可以按任意顺序来扩展它们。

而这里采用的原则是先生成的结点先扩展。

算法运行结果图算法图是关于个节点进行算法考虑长度为的结点的每种可能的状态。

因此，对于同层结点来说，求解问题的价值是相同的，我们可以按任意顺序来扩展它们。

这里采用的原则是先生成的结点先扩展。

深度优先算法运行结果图深度优先搜索图是关于个节点进行深度优先搜索的运行结果，从节点开始，访问与他相邻的节点,然后再访问与节点相邻的节点，重复此过程直到找到目标节点为止。

深度优先搜索算法中，从起始结出发，访问它的任邻接结点再从出发，访问与邻接但还没有访问过的顶点然后再从出发，进行类似的访问„„如此进行下去，直至所有的邻接结点都被访问为止,如果此时还没有找到目标结点，则退回步，退到前次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。

如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问如果没有，就再退回步进行搜索。

重复上述过程，直到找到目标结点或图中所有顶点都被访问过为止。

对于多个邻接结点，求解问题的价值是相同的，因此我们可以按任意顺序来扩展它们。

而这里采用的原则是先生成的结点先扩展。

算法运行结果图算法图是关于个节点进行算法的运行结果。

最为核心的过程，在于每次选择下个当前搜索点时，是从所有已探知的但未搜索过点中可能是不同层，亦可不在同条支路上，选取值最小的结点进行展开。

而所有已探知的但未搜索过点可以通过个按值升序的队列即优先队列进行排列。

这样，在整体的搜索过程中，只要按照类似广度优先的算法框架，从优先队列中弹出队首元素值，对其可能子结点计算和值，直到优先队列为空无解或找到终止点为止。

算法的总体比较与分析对于广度优先搜索算法，当结点到跟结点的费用和结点的深度成正比时，特别是当每结点到根结点的费用等于深度时，用广度优先法得到的解是最优解，但如果不成正比，则得到的解不定是最优解，而般情况下广度优先搜索算发都能找到最优解，但必须遍历搜的的分枝。

广度优先搜索算法，般需要存储产生的所有结点，占的存储空间要比深度优先大得多，由于对空间的大量需求，因此广度优先算法并不适合解非常大的问题。

对于深度优先搜索算法，般来说时间复杂度大但空间复杂度小，不保留全部结点的深度优先搜索法，由于把扩展望的结点从数据库中弹出删除，这样，般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为种有效的算法。

从输出结果方面看，深度优先搜索算法般只能找到满意解，但能很快找到接近解，可能不必遍历所有分枝。

在更多的情况下，深度优先搜索算法也是比较好的方案。

深度搜索与广度搜索的控制结构和产生系统很相似，唯的区别在于对扩展节点选取上。

这两种算法每次都扩展个节点的所有子节点，而不同的是，深度搜索下次扩展的是本次扩展出来的子节点中的个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。

比较深度优先和广度优先两种搜索算法可以看出，广度优先搜索法般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索算法法要快些。

总之，般情况下，深度优先搜索法占内存少但速度较慢，广度优先搜索算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。

因此在选择用哪种算法时，要综合考虑，决定取舍。

广度优先搜索算法和深度优先搜索算法均属于盲目型搜索，也就是说，它不会选择哪个结点在下次搜索中更优，而去跳转到该结点进行下步的搜索，因此他们的效率非常的低。

在运气不好的情形中，均需要试探完整个解集空间,显然，只能适用于问题规模不大的搜索问题中。

而算法与广度优先和深度优先这类盲目型搜索最大的不同，就在于当前搜索结点往下选择下步结点时，可以通过个启发函数来进行选择，选择代价最少的结点作为下步搜索结点而跳转其上。

算法的控制结构与广度搜索的十分类似，只是每次扩展的都是当前待扩展节点中值最小的个，如果扩展出来的节点与已扩展的节点重复，则删去这个节点。

如果与待扩展节点重复或这个节点的估价函数值较小，则用其代替原待扩展节点。

算法利用对问题的了解和对问题求解过程的了解,寻求种有利于问题求解的启发信息,从而利用这些启发信息去搜索最优路径它不用遍历整个地图,而是每步搜索都根据启发函数朝着个方向搜索当地图很大很复杂时,它的计算复杂度大大优于其他启发式算法,是种搜索速度非常快效率非常高的算法但是,相应的算法也有它的缺点启发性信息是人为加入的,有很大的主观性,直接取决于操作者的经验,对于不同的情形要用不同的启发信息和启发函数,且他们的选取难度比较大。

当实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

因此写出好的评估函数，时算法的关键。

算法与广度优先和深度优先的联系在于，当时，该算法类似于，当时，该算法类似于,这点，可以通过搜索树的具体过程中将设为或将设为而得到。

结论本文描述了最短路径算法的些步骤和实际应用，归纳了每个算法的适用情况和优缺点，以及算法之间的些关系。

对于最短或最少问题应该选用广度优先算法,遍历和求所有问题的时候则应该选用深度优先算法，这两种算法虽然好用，但是由于时间和空间的局限性，以至于它们只能解决规模不大的搜索问题，对规模十分大的情况下，他们的效率非常的低，甚至不能完成，那么就要用到启发式搜索算法算法，算法是种最好优先的算法，适合于小规模大规模以及超大规模的问题，但启发式搜索算法同时具有很大的主观性，它的优劣取决于编程者的经验，以及选用的启发式函数，所以用算法编写个优秀的程序，难度相应是比较大的。

每种算法都有自己的应用范围，对于不同的问题则应该选用不同的算法。

参考文献圣群,滕忠坚,洪亲,陈清华四种最短路径算法实例分析电脑知识与技术学术交流,树林,尹玉妹图的最短路径算法及其在网络中的应用软件导刊,文海,徐荣聪几种最短路径的算法及比较福建电脑，春燕两种最短路径算法的比较电脑知识与技术，苏男,伟,文生最短路径算法的比较系统工程与电子技术,凤生,李天志所有最短路径的求解算法计算机工程与科学,臣波,刘润涛种基于的最短路径算法哈尔滨理工大学学报,凤生求最短路径的新算法计算机工程与科学,杨长保,王开义,马生忠种最短路径分析优化算法的实现吉林大学学报信息科学版,亚松实现基于算法的最短路径科技信息科学教研谢辞光阴似箭日月如梭，美好的大学生活在这骄阳似火的季节即将画上个句号，而于我的人生却只是个逗号，我将面临又次新的征程的开始。

同时经过几个月的学习与努力，我的毕业论文也即将完成。

本次论文的撰写，对即将毕业的我也是次难得的锻炼机会，让我的学习能力和实际应用能力都有很大的提高。

在本次毕业设计中，曾遇到过很多问题，在老师和同学的帮助下，都得到了很好的解决。

其中，导师渊博的专业知识，严谨的治学态度，精益求精的工作作风，诲人不倦的高尚师德，对我影响深远。

不仅使我掌握了基本的研究方法，还使我明白了许多待人接物与为人处世的道理。

他对我进行了无私的指导和帮助，不厌其烦的进行论文的批注，倾注了导师大量的心血。

在此，我衷心的感谢我的指导老师董峦老师和学校给予的良好环境以及关心我的人，是你们的关心让我从校园生活慢慢的走向社会，走向未来。

个人的成长绝不是件孤立的事，没有别人的支持与帮助是绝对办不到。

我感谢