Floyd算法求解最短路径问题(完整程序代码)

交通运输学院课程设计1引言在图论中经常会遇到这样的问题，在一个有向图里求出任意两个节点之间的最短距离。当节点之间的权值是正值的时候，我们可以采用Dijkstra算法，用贪心策略加于解决。但当节点之间的权值有负数的时候，Dijkstra就行不通了，这里介绍另外一种算法—Floyd最短路径算法。对于任意图，选择存储结构存储图并实现FLOYD算法求解最短路经。将问题分解，分解为两方面。一是对于任意图的存储问题，第二个是实现FLOYD算法求解最短路经。首先对于图的创建选择合适的存储结构进行存储，对于合适的存储结构可以简化程序。本实验采用邻接矩阵存储。然后是实现FLOYD算法求解最短路经，在FLOYD算法中路径的长度即是图中两定点间边的权值，FLOYD算法要求输出任意两个顶点间的最短路径，而且经过的顶点也要输出。考虑到问题的特殊性，采用一个二维数组和一个三维数组进行存储。二维数组存储最短路径，三维数组存储路径经过的顶点，在进行适当的算法后对这两个数组进行输出即可。通过问题的分解，逐个解决，事先所要求的程序。最短路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。传统的最短路径算法主要有Floyd算法和Dijkstra算法。Floyd算法用于计算所有结点之间的最短路径。Dijkstra算法则用于计算一个结点到其他所有结点的最短路径。Dijkstra算法是已经证明的能得出最短路径的最优解，但它的效率是一个很大的问题。对于具有n个结点的一个图，计算一个结点到图中其余结点最短路径的算法时间复杂度为O(n2)。对于一座大中型城市，地理结点数目可能达到几万个到几十万个，计算最短路径的时间开销将是非常巨大的。本文根据吴一民老师的建议，分析当前存在的各种求最短路径的算法，提出一种新的基于层次图的最短路径算法，即将一个平面图划分若干子图，子图抽象为一个高层图。最短路径的计算首先在高层图中进行，缩小了最短路径的查找范围，降低了最短路径计算的时间开销。由于可以动态计算子图间的阻抗函数，算法可适用于动态交通诱导系统。设计目的（1）培养学生分析解决问题的能力，掌握java语言的程序设计方法；（2）通过课程设计实践，训练并提高学生在统筹全局、结构设计、查阅设计资料和计算机编程方面的能力；（3）提高学生实践论文撰写能力。任务与要求：(1)理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订；(2)课程设计报告（论文）包括要求的作业。交通运输学院课程设计2第一章Floyd算法1.1最短路的定义最短路径问题是图论研究中的一个经典算法，旨在寻找图中两结点之间的最短路径。算法的具体形式包括：确定起点的最短路径问题即已知起始结点，求最短路径问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路经反转的确定起点的问题。确定起点终点的最短路径问题即已知起点和终点求两结点之间的最短路径。求距离最短路径问题求图中所有的最短路径。用于解决最短路径问题的算法被称为最短路径算法。单源最短路定义：给定一个赋权有向图G=（V,E）,记G中每一条弧aij=(vi,vj)上的权为W(aij)=Wij,有给定G中的一个起点s和重点t，设p是G中从s到t的一条路，则定义路径p的权是p中有弧的权之和，记为W（p），即:W（p）=(,)ViVjpWij又若p*是图G中从s到t的一条路径，且满足W（p*）=min{W（p）|p为Vs到Vt的路}试中对G的所有从s到t的路p取最小，则称p*为从s到t的最短路，W（p*）为s到t的最短距离。在一个图G中，求从s到t的最短路径和最短距离问题就称为最短路径问题。1.2Floyd的定义与思想1.2.1Floyd算法的定义Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。1.2.2Floyd算法的思想利用一个三重循环产生一个存储每个结点最短距离的矩阵.弗洛伊德算法仍然使用图的邻接矩阵arcs[n+1][n+1]来存储带权有向图。算法的基本思想是:设置一个nxn的矩阵A(k)，其中除对角线的元素都等于0外，其它元素a(k)[i][j]表示顶点i到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为∞，当K=0时,A(0)[i][j]=arcs[i][j]，以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：交通运输学院课程设计3第一步，让所有边上加入中间顶点1，取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的值，完成后得到A(1)，第二步，让所有边上加入中间顶点2，取A[i][j]与A[i][2]+A[2][j]中较小的值，完成后得到A(2)…，如此进行下去，当第n步完成后，得到A(n)，A(n)即为我们所求结果,A(n)[i][j]表示顶点i到顶点j的最短距离。因此，弗洛伊德算法可以描述为:A(0)[i][j]=arcs[i][j];//arcs为图的邻接矩阵A(k)[i][j]=min{A(k-1)[i][j],A(k-1)[i][k]+A(k-1)[k][j]}其中k=1,2,…,n定义一个n阶方阵序列：D(-1),D(0),…,D(n-1).其中D(-1)[i][j]=G.arcs[i][j]；D(k)[i][j]=min{D(k-1)[i][j]，D(k-1)[i][k]+D(k-1)[k][j]},k=0,1,…,n-1D(0)[i][j]是从顶点vi到vj,中间顶点是v0的最短路径的长度,D(k)[i][j]是从顶点vi到vj,中间顶点的序号不大于k的最短路径长度,D(n-1)[i][j]是从顶点vi到vj的最短路径长度。1.3Floyd算法描述通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。a)初始化：D[u,v]=A[u,v]b)Fork:=1tonFori:=1tonForj:=1tonIfD[i,j]D[i,k]+D[k,j]ThenD[I,j]:=D[I,k]+D[k,j];c)算法结束：D即为所有点对的最短路径矩阵从图的带权邻接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造交通运输学院课程设计4出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同还可引入一个后继节点矩阵path来记录两点间的最短路径。采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);其状态转移方程如下：map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}map[i,j]表示i到j的最短距离K是穷举i,j的断点map[n,n]初值应该为0，或者按照题目意思来做。当然，如果这条路没有通的话，还必须特殊处理,比如没有map[i,k]这条路1.4Floyd算法过程在图论中经常会遇到这样的问题，在一个有向图里，求出任意两个节点之间的最短距离。我们在离散数学、数据结构课上都遇到过这个问题，在计算机网络里介绍网络层的时候好像也遇到过这个问题，记不请了...但是书本上一律采取的是Dijkstra算法，通过Dijkstra算法可以求出单源最短路径，然后逐个节点利用Dijkstra算法就可以了。不过在这里想换换口味，采取RobertFloyd提出的算法来解决这个问题。下面让我们先把问题稍微的形式化一下：如果有一个矩阵D=[d(ij)]，其中d(ij)0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。编写一个程序，通过这个距离矩阵D，把任意两个城市之间的最短与其行径的路径找出来。我们可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个城市而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有d(ij)d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。所以我们就可以用三个for循环把问题搞定了，但是有一个问题需要注意，那就是for循环的嵌套的顺序：我们可能随手就会写出这样的程序，但是仔细考虑的话，会发现是有问题for(inti=0;in;i++)for(intj=0;jn;j++)for(intk=0;kn;k++)问题出在我们太早的把i-k-j的距离确定下来了，假设一旦找到了i-p-j最短的距离后，i到j就相当处理完了，以后不会在改变了，一旦以后有使i到j的更短的距离时也不能再去更新了，所以结果一定是不对的。所以应当象下面一样来写程序：交通运输学院课程设计5for(intk=0;kn;k++)for(inti=0;in;i++)for(intj=0;jn;j++)这样作的意义在于固定了k，把所有i到j而经过k的距离找出来，然后象开头所提到的那样进行比较和重写，因为k是在最外层的，所以会把所有的i到j都处理完后，才会移动到下一个k，这样就不会有问题了，把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=空值。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。1.5Floyd算法优缺点分析Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次DijkStra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点：时间复杂度比较高，不适合计算大量数据。第二章邻接矩阵2.1邻接矩阵的定义邻接矩阵（AdjacencyMatrix）：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：2.2邻接矩阵的特点无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+...+(n-1)=n(n-1)/2个单元。无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。用邻接矩阵表示图，很容易确