图论最短路径算法的图形化演示及系统设计

《图论最短路径算法的图形化演示及系统设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图论最短路径算法的图形化演示及系统设计摘要：关于图论最短路径算法的图形化演示程序的开发和系统的设计。这里首先介绍最短路径问题的概念和最短路径的算法(指迪杰斯特拉(Dijkstra)f法和弗洛伊德(Floyd)算法)。然后，在Eclipse和JDK1.6环境下开发演示最短路径问题算法的流程。最后，运行系统演示程序进行正确性验证。该算法演示程序简单易用、清晰明了、形象而生动的演示了算法。关键词：图论；最短路径；Dijkstra；Floyd；演示系统中图分类号：TP393文献标识码：A文章编号：1009-3044

2、(2016)18-0159-02图论问题始终渗透整个计算机科学，可以说每个编程者都不可避免地与图打交道，因而图论算法对计算机科学至关重要。它的应用领域非常多。例如，图论可以应用于电路网络分析、运筹学、网络、信息论、控制论以及计算机科学等各个领域。我们知道最短路径问题是网络理论中应用最为广泛的问题之一。而这里介绍的最短路径算法是图论算法中重要的一支。最短路径算法可以解决许多问题，例如：线路安排、管道铺设、路由选择、地址选择、设备更新、广场布局、时变拓扑网络等。我们这里研宄的就是最短路径问题的算法，具体指的是迪

3、杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。这里通过开发一个系统演示程序来生动的阐述迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。该系统演示程序简单易用、清晰明了、界面友好、非常实用。该系统演示程序是在Eclipse和JDK1.6的环境下用java语言开发而成的。它为解决最短路径问题提供了一个简单实用的平台。1最短路径问题定义：我们给定一个带权重的有向图G=（V，E）和权重函数w:E—R,该权重函数将每条边映射到实数值的权重上。图中一条路径p=的权重w（p）是构成该路径的

4、所有边的权重之和：w（p）=Ew（vi-1，vi），i=l，2，3…，ko假设一条从节点m到节点n的最短路径权重为W（m,n）,且W（m，n）计算如下：①如果存在一条从节点m到节点n的路径，贝lj:W（m:n）=min{w（p）

5、p是一条从节点m到节点n的路径};②否则，W（m，n）二①。从节点m到节点n的路径p，如果满足w（p）=W（m，n）则该路径p即为从节点m到节点n的最短路径。求从节点m到节点n的最短路径和最短距离的问题就是最短路径问题。2最短路径算法2.1弗洛伊德算法思想我们使用三重for循环产生

6、一个矩阵来记录每个节点间的最小距离。对于弗洛伊德(Floyd)算法我们使用矩阵Juzhen[i][j](i，j=l，2，n+1)存储有向图的权重值。所以，其基本思想为：初始化一个n阶矩阵A(k)，其主对角线上的元素初始化为0,非对角线上的元素初始化A(k)[i][j],其中每一个A(k)[i][j]是节点i到节点j的权重值，k是运算到第几步。算法一开始，我们选择任意两个节点分别作为起始点和终止点，若他们之间有边则取其权重值作为他们的路径长度，若无权重边，则令其路径长度为…，再有k=0时，我们初始化A(k)[

7、i][j],此时A(0)[i][j]=Juzhen[i即，将路径上的节点加入集合S中，之后再选择不在集合S中但能构成最短路径的节点，使其加入集合S，如果在i节点和j节点之间增加了中间节点后，使得节点i到节点j的路径比A(k)[i][j]小，就用新的权重值去更新A(k)[i][j]。因此，弗洛伊德(Floyd)算法步骤如下：(1)当k=0时，A(0)[i][j]=Juzhen剛];其中Juzhen[i][j]为邻接矩阵(2)当k=i+l，i+2，…，j时，A(k)[i][j]=min{A(k-1)[i][j]

8、,A(k-1)[i][k]+A(k-1)[k][j]}其中A(k)[i]U]表示节点点vi到vj，中间节点的不大于k的最短路径的长度，这里求的是中间节点的不大于n的最短路径的长度即A(n)[i][j]。因而，其算法可以描述为：(1)令D[i][j]:A[i]U](2)for(k二1;kD[i][k]+D[k][j]){D[i][j]=D[i][k]+D[k]U]}(3)算法结束后矩阵D存储了所有节点之间的最短路径值。2.2迪杰斯特拉算法的思想Dijkstra算法解决的是带权重的有向图上单源点最短路径的问题。

9、该算法要求所有边的权重都为非负值。Dijkstra算法把图中所有的节点分为两组：设集合S表示己经求出的最短路径上的节点的集合；集合T=V-S表示在集合V中而在节点S之外的所有的节点的集合。然后把集合T中节点按权值非减的次序排序，并按此顺序依次加入到集合S里。除此之外，还要满足如下两个条件：第一，从出发点vO到集合S中每一个节点的最短路径长度A(k)[i][j]都应该小于或者等于从节点vO到集合T中所有节点的权重值