网络最短路径问题与应用研究

《网络最短路径问题与应用研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、比较活跃的一门学科。早在20世纪60年代，对最短路径问题的研究已经卓有成效，且在1959年由荷兰著名计算机专家E.W.Dijkstra第一次提出了对赋权图(0)“>问题的有效算法,该算法不仅能够求出99U任意两顶点间的最短路,而且能够求解图中某一特定顶点到其它各顶点的最短路。该算法的复杂度为顶点数平方的数量级，当针对大规模的网络模型时，顶点数和边数较多，算法的计算量则较大，花费时间更多。因此，Dijkstra算法在理论上是正确的，但在实际应用中不尽人意。后来海斯分析了Dijkstra算法的特性和思想，提出了海斯算法。但对于含有负权的图的最短路问题，这两种算法都无能为力，于是由Ford

2、提出了一种能够有效解决含有负权的最短路问题的算法，即Ford算法【5】，但在现实牛活中所遇到的问题大都不含负权,所以在边值非负(0)">的情况下选择Dijkstra算法。99U1968年，人们开发出A*算法⑹，该算法主要用在人工智能领域，是对地图的一种搜索策略，尤其适用于公交查询系统，并使用启发式函数来评估对搜索过程中产生的分支的好坏，以便选取最佳的分支进行搜索。A*算法最为核心的部分在于一个估价函数f(n)=g(n)+h(n)of(n)由两个部分组成，其中g(n)表示从起始顶点到达当前顶点的耗费，而h(n)是最为重要的一部分，表示从当前顶点到达目标顶点耗费的估值，要求评估函数满足h

3、(n)<=h*(n)(其中h*(n)为实际问题的代价值)。其必须满足两个条件：(1)f(n)必须保持单调递增。(2)h(n)必须小于或等于实际从当前节点到目标节点的最低⑺耗费h*(n)o在这里，如果g(n)=0,贝U算法类似于深度优先算法(DFS)；如果h(n)=0,则算法类似于广度优先算法(BFS)；如果h(n)=0,只要求解g(n),即源点到任意顶点的最短路径，则转化为了单源最短路径问题，即Dijkstra算法。由于已经有了一定的先验知识，因此”算法在计算时间上比他的遍历搜索的速度更快，但它并不一定能够搜索到最短路径，只能是相对短的路径。Z后意大利学者MDorigo,VManie

4、zzo,AColorni等在20世纪90年代初，通过模拟蚂蚁搜索路径的行为，首次提岀了蚂蚁算法【8】，该算法具有记忆功能，选择某路径的次数越多，说明此路径是比较优的路径，其信息素的值也越大，为以后选择路径提供必要的信息。同样，若某系统使用的时间越长，所提供的信息越全面，越准确，则系统也越智能化。在众多求解最短路径的方法中，公认的经典算法有两个：迪杰斯特拉(Dijkstra)及弗罗伊徳(Floyd)算法。无论是哪一个算法，其解决实际问题的基本思想都是转化模型：他们都将一个有向或无向图描述成一个网络，并将各点间的关联信息抽彖为图的节点邻接矩阵。经过这样一个模型转化以后，搜索最短路径只需以

5、矩阵为基础，对图的各节点进行遍历，直到判别目标值为最小即可。Dijkstra算法是图论中求解最短路径的基本方法，同时也是其它算法【9］的基础。目前，对于求赋权图屮任意两结点Z间的最短路径一般有两种方法：(1)每次以一个结点为源点，重复执行n次Dijkstra算法。(2)Floyd算法。这个算法是由弗洛伊徳在1962年提出的，尽管在时间复杂度上与上述算法相同，但其形式上简单，实际运算效果远远好于前者。近几年来，信息技术和互联网应用飞速发展，社会信息日益不断膨胀。大量的复杂应用问题时时刻刻以多种不同的形式传播衍变，这使得人们对最短路径算法的研究耍求越来越高。计算机网络与通信、分布式处理和

6、智能交通系统【"］等的兴起给这个传统的研究课题带来了新的转折，这些要求解决最短路径问题的领域都以复杂网络的结构呈现。还有，现在的算法都是针对两点间的小规模网络，对于大规模网络如何解决成为重点，因此，对最短路问题的研究仍具有重要理论意义和实际意义，发展前景任为广阔。1.3论文研究内容及结构安排本文在深入分析已有算法的基础上，针对小规模无回路网络最短路径这一问题，引出了两种新的简单易行的算法，文中并对每种算法都给出了算法步骤，复杂度分析，可行性验证，以及具体实例分析，并以比较为目的说明了算法的优缺点，最后得出算法不仅思想简便、易于操作，同时有效的降低了算法吋间复杂度，是计算小规模无冋路网

7、络的行之有效的算法，最后通过计算机语言对其进行了有力的验证，得到的结果完全一致。本文的具体内容安排如下：第一章绪论。阐述了论文的研究背景及意义，并概括了最短路径问题的研究冃的、研究现状，以及给出本文的内容和结构安排。第二章最短路径问题及其相关算法。介绍了最短路径问题的一些基本概念、图的相关定义，并给出了求解最短路径问题的几种经典算法，如Dijkstra算法、Bellman-Ford算法，SPFA算法，Floyd算法等，并对这四种算法的基木思想和算法步骤做了