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

交通运输学院课程设计引言在图论中经常会遇到这样的问题，在一个有向图里求出任意两个节点之间的最短距离。当节点之间的权值是正值的时候，我们可以采用Dijkstra算法，用贪心策略加于解决。但当节点之间的权值有负数的时候，Dijkstra就行不通了，这里介绍另外一种算法Floyd最短路径算法。对于任意图，选择存储结构存储图并实现FLOYD算法求解最短路经。将问题分解，分解为两方面。一是对于任意图的存储问题，第二个是实现FLOYD算法求解最短路经。首先对于图的创建选择合适的存储结构进行存储，对于合适的存储结构可以简化程序。本实验采用邻接矩阵存储。然后是实现FLOYD算法求解最短路经，在FLOYD算法中路径的长度即是图中两定点间边的权值，FLOYD算法要求输出任意两个顶点间的最短路径，而且经过的顶点也要输出。考虑到问题的特殊性，采用一个二维数组和一个三维数组进行存储。二维数组存储最短路径，三维数组存储路径经过的顶点，在进行适当的算法后对这两个数组进行输出即可。通过问题的分解，逐个解决，事先所要求的程序。最短路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。传统的最短路径算法主要有Floyd算法和Dijkstra算法。Floyd算法用于计算所有结点之间的最短路径。Dijkstra算法则用于计算一个结点到其他所有结点的最短路径。Dijkstra算法是已经证明的能得出最短路径的最优解，但它的效率是一个很大的问题。对于具有n个结点的一个图，计算一个结点到图中其余结点最短路径的算法时间复杂度为O(n2)。对于一座大中型城市，地理结点数目可能达到几万个到几十万个，计算最短路径的时间开销将是非常巨大的。本文根据吴一民老师的建议，分析当前存在的各种求最短路径的算法，提出一种新的基于层次图的最短路径算法，即将一个平面图划分若干子图，子图抽象为一个高层图。最短路径的计算首先在高层图中进行，缩小了最短路径的查找范围，降低了最短路径计算的时间开销。由于可以动态计算子图间的阻抗函数，算法可适用于动态交通诱导系统。设计目的（1）培养学生分析解决问题的能力，掌握java语言的程序设计方法；（2）通过课程设计实践，训练并提高学生在统筹全局、结构设计、查阅设计资料和计算机编程方面的能力；（3）提高学生实践论文撰写能力。任务与要求： (1) 理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订；(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）=又若p*是图G中从s到t的一条路径，且满足W（p*）=minW（p）|p为Vs到Vt的路试中对G的所有从s到t的路p取最小，则称p*为从s到t的最短路，W（p*）为s到t的最短距离。在一个图G中，求从s到t的最短路径和最短距离问题就称为最短路径问题。1.2 Floyd的定义与思想 1.2.1 Floyd算法的定义 Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。 1.2.2 Floyd 算法的思想利用一个三重循环产生一个存储每个结点最短距离的矩阵.弗洛伊德算法仍然使用图的邻接矩阵arcsn+1n+1来存储带权有向图。算法的基本思想是:设置一个n x n的矩阵A(k)，其中除对角线的元素都等于0外，其它元素a(k)ij表示顶点i到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为，当K=0时, A (0)ij=arcsij，以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为： 第一步，让所有边上加入中间顶点1，取Aij与Ai1+A1j中较小的值作Aij的值，完成后得到A(1)，第二步，让所有边上加入中间顶点2，取Aij与Ai2+A2j中较小的值，完成后得到A(2)，如此进行下去，当第n步完成后，得到A(n)，A(n)即为我们所求结果,A(n)ij表示顶点i到顶点j的最短距离。因此，弗洛伊德算法可以描述为: A(0)ij=arcsij; /arcs为图的邻接矩阵 A(k)ij=minA(k-1) ij,A(k-1) ik+A(k-1) kj其中 k=1,2,n定义一个n阶方阵序列： D(-1), D(0), , D(n-1). 其中 D(-1) ij = G.arcsij； D(k) ij = min D(k-1)ij，D(k-1)ik + D(k-1)kj , k = 0,1, n-1 D(0) ij是从顶点vi 到vj , 中间顶点是v0的最短路径的长度, D(k) ij是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径长度, D(n-1)ij是从顶点vi 到vj 的最短路径长度。1.3 Floyd算法描述 通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。a) 初始化：Du,v=Au,v b) For k:=1 to n For i:=1 to n For j:=1 to n If Di,jDi,k+Dk,j Then DI,j:=DI,k+Dk,j; c) 算法结束：D即为所有点对的最短路径矩阵 从图的带权邻接矩阵A=a(i,j) nn开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j 列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同 还可引入一个后继节点矩阵path来记录两点间的最短路径。 采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n3); 其状态转移方程如下： mapi,j:=minmapi,k+mapk,j,mapi,jmapi,j表示i到j的最短距离 K是穷举i,j的断点 mapn,n初值应该为0，或者按照题目意思来做。当然，如果这条路没有通的话，还必须特殊处理,比如没有mapi,k这条路 1.4 Floyd算法过程在图论中经常会遇到这样的问题，在一个有向图里，求出任意两个节点之间的最短距离。我们在离散数学、数据结构课上都遇到过这个问题，在计算机网络里介绍网络层的时候好像也遇到过这个问题，记不请了. 但是书本上一律采取的是Dijkstra算法，通过Dijkstra算法可以求出单源最短路径，然后逐个节点利用Dijkstra算法就可以了。不过在这里想换换口味，采取Robert Floyd提出的算法来解决这个问题。下面让我们先把问题稍微的形式化一下： 如果有一个矩阵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(int i=0; in; i+) for(int j=0; jn; j+) for(int k=0; kn; k+) 问题出在我们太早的把i-k-j的距离确定下来了，假设一旦找到了i-p-j最短的距离后，i到j就相当处理完了，以后不会在改变了，一旦以后有使i到j的更短的距离时也不能再去更新了，所以结果一定是不对的。所以应当象下面一样来写程序： for(int k=0; kn; k+) for(int i=0; in; i+) for(int j=0; jn; j+) 这样作的意义在于固定了k，把所有i到j而经过k的距离找出来，然后象开头所提到的那样进行比较和重写，因为k是在最外层的，所以会把所有的i到j都处理完后，才会移动到下一个k，这样就不会有问题了，把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则Gi,j=d，d表示该路的长度；否则Gi,j=空值。 定义一个矩阵D用来记录所插入点的信息，Di,j表示从Vi到Vj需要经过的点，初始化Di,j=j。 把各个顶点插入图中，比较插点后的距离与原来的距离，Gi,j = min( Gi,j, Gi,k+Gk,j )，如果Gi,j的值变小，则Di,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.5 Floyd算法优缺点分析Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次DijkStra算法。 优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单； 缺点：时间复杂度比较高，不适合计算大量数据。第二章 邻接矩阵2.1 邻接矩阵的定义邻接矩阵（Adjacency Matrix）：是表示顶点之间相邻关系的矩阵。设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列非零元素个数之和。 用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。 2.3 邻接矩阵的表示方法2.3.1 图的邻接矩阵表示法 在图的邻接矩阵表示法中： 用邻接矩阵表示顶点间的相邻关系 用一个顺序表来存储顶点信息 2.3.2 图的邻接矩阵(Adacency Matrix) 设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵： Ai,j=1 若（Vi,Vj）或者是E(G)中的边； Ai,j=0 若（Vi,Vj）或者不是E(G)中的边。若G是网络，则邻接矩阵可定义为： Ai,j=Wij 若（Vi,Vj）或属于E（G） AI,j=0或 若（Vi,Vj）或不属于E（G） 其中： Wij 表示边上的权值; 表示一个计算机允许的、大于所有边上权值的数。 【例】下面带权图的两种邻接矩阵分别为A 3 和A 4 。 2.3.3邻接矩阵的特点：无向图的邻接矩阵一定是一个对称矩阵。无向图的邻接矩阵的第i行（或第i列）非零元素（或非无穷元素）个数为第i个顶点的度D（vi）.有向图的邻接矩阵的第i行非零元素（或非无穷元素）个数为第i个顶点的度OD(vi)，第i列非零元素（或非无穷元素）个数就是第i个顶点的入度ID（vi）。邻接矩阵表示图，很容易确定图中任意两个顶点之间是否有边相连。容易判断两个顶点之间是否有长度为m的路径相连。邻接矩阵表示法的缺点：邻接矩阵占用的存储单元个数只与图中的结点个数有关，而与边的数目无关。一个n各节点的图，若其边数比n平方少得多，那么邻接矩阵中存在大量的无用的单元。第三章 Floyd算法实例3.1 Floyd算法实例现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表城市之间的距离。求每个城市的最短距离【输入】 用V表示各个城市，输入顶点Vi与Vj，【输出】 输出所有可能连接的城市的最短距离。最短路径算法的作用就是在图中找出任意两点间最短距离的途径，比如可以在地图上找出任两个城市之间路程最短的那条路径。有两种算法可以实现，一种是迪杰斯特拉（Dijkstra）算法，一种是弗洛伊德（Floyd）算法。弗洛伊德（Floyd）算法过程：、用Dvw记录每一对顶点的最短距离。、依次扫描每一个点，并以其为基点再遍历所有每一对顶点D的值，看看是否可用过该基点让这对顶点间的距离更小。算法理解：最短距离有三种情况：、两点的直达距离最短。（如下图）、两点间只通过一个中间点而距离最短。（图）、两点间用通过两各以上的顶点而距离最短。（图）对于第一种情况：在初始化的时候就已经找出来了且以后也不会更改到。对于第二种情况：弗洛伊德算法的基本操作就是对于每一对顶点，遍历所有其它顶点，看看可否通过这一个顶点让这对顶点距离更短，也就是遍历了图中所有的三角形（算法中对同一个三角形扫描了九次，原则上只用扫描三次即可，但要加入判断，效率更低）。对于第三种情况：如下图的五边形，可先找一点（比如x，使=2），就变成了四边形问题，再找一点（比如y,使=2），可变成三角形问题了（v,u,w），也就变成第二种情况了，由此对于n边形也可以一步步转化成四边形三角形问题。（这里面不用担心哪个点要先找哪个点要后找，因为找了任一个点都可以使其变成（n1）边形的问题）。第四章 结论通过Floyd算法求解图中顶点的最短路径问题实验，更加深入的了解了数据结构与算法在各个领域的应用。比如图的最短路径问题，衍生为校内导游图，乘客路径问题等等的实际性的日常问题。在该实验的求解过程中，把问题分解为三个部分来解决。首先考虑的是对于任意图的存储问题。在数据结构与算法中，介绍了多种图的存储结构，有邻接矩阵存储，邻接表存储以及十字链表等等存储方法。考虑到本实验要对图进行求解路径，采用邻接矩阵存储。邻接矩阵存储图很容易判断图中两个顶点是否相连。例如，判断Vi和Vj是否相连，只需检查Gij是否等于零，如果该、等于零则不相连。以上是两个顶点是否直接相连的算法。然后是路径问题，对于任意两个顶点，路径也就分为三个情况，即直接相连是最短路径，经过某几个顶点后，经过的路径是最短路径，还有这两个顶点之间没有最短路径。对于直接相连的路径就是最短路径，直接输出即可。例如ab直接相连，且最短路径就是直接路径，路径长度为10，输出a到b的路径就为：ab，路径长度为10。经过某几个定点后的路径是最短路径，用二维数组length先保存最短路径长。若lengthijlengthik+lengthkj则经过k点后i到j得的路径短一些，此时将lengthik+lengthkj赋值给lengthij，用二维数组path记录下经过的点k，这样在循环里对整个路径都进行一边比较，保存下最短路径以及这些路径经过的顶点。对于两点之间没有路径的问题，lengthij一直为最大值，若有路径则同第二步，没有则lengthij一直保持不变。最后待解决的问题就是输出任意两点之间的最短路径，从i到j的最短路径全部保存在length中，要向输出任意两点之间的最短路径长度并不难，但如何输出之间经历过的定点呢?在存入的时候首先存入p是离j最近的一点，然后是离p最近的一点，依次存入，最后一个存入的是离i最近的顶点，所以输出的时候必须倒序输出。采用向前递归算法实现。在3x3循环里，如果lengthij=0或者lengthij=INF（INF是自定义的最大值）都是没有路径的，lengthij=0此时若i=j，则是定点无路径。若lengthij=INF则i到j没有路径。如果lengthij=0但是i!=j，此时说明i到j的最短路径是0，路径是存在的，应该另外考虑这种情况，同下面的输出一致。若以上三种情况都不符合则执行正常的输出操作，输出从i到j经过的顶点，并输出路径长度。通过上述三个步骤，解决了Floyd算法的最短路径问题。参考文献1 朱福喜编著.面向对象与Java程序设计.北京：清华大学出版社，20082 焦永兰主编.管理运筹学.北京：中国铁道出版社，20023 黄国瑜，叶乃菁编著。数据结构。清华大学出版社，20054 朱福喜，唐晓军编著.Java编程技巧与开发实例.北京：清华大学出版生，20045 王昆仑，李红.数据结构与算法.北京:中国铁道出版社，2006.56 侯风巍，杨永田.数据结构要点精细.北京航空航天大学出版社，2006.8附录1 程序流程图：2 程序实现代码：package Example; import java.awt.*; import java.awt.event.*; import java.awt.geom.Ellipse2D; import javax.swing.*; public class testpaint extends JFrame implements ActionListener int length = null; public void Floyd(int G) int max =9999; int row = G.length; / 图G的行数 int A = new introwrow;/ 定义任意两点之间经过的点 intPath = new introw;/ 记录一条路径 length = new introwrow; for (int i = 0; i row; i+) / 处理图两点之间的路径 for (int j = 0; j row; j+) if (Gij = 0) Gij = max; / 没有路径的两个点之间的路径为默认最大 if (i = j) Gij = 0; / 本身的路径长度为0 for (int i = 0; i row; i+) / 初始化为任意两点之间没有路径 for (int j = 0; j row; j+) Aij = -1; for (int i = 0; i row; i+) Pathi = -1; / 假设任意两点之间的没有路径 for (int m = 0; m row; +m) for (int n = 0; n row; +n) lengthmn = Gmn; for (int u = 0; u row; +u) for (int m = 0; m row; +m) for (int n = 0; n lengthmu + lengthun) lengthmn = lengthmu + lengthun;/ 如果存在更短路径则取更短路径 Amn = u;/ 把经过的点加入 for (int i = 0; i row; i+) / 求出所有的路径 int point = new int1; for (int j = 0; j row; j+) point0 = 0; Pathpoint0+ = i; outputPath(A, i, j, Path, point); void outputPath(intA, int i, int j, intPath, int point) / 输出i到j的路径的实际代码,point记录一条路径的长度 if (i = j) return; if (Aij = -1) Pathpoint0+ = j; else outputPath(A, i, Aij, Path, point); outputPath(A, Aij, j, Path, point); int shuzu=new int66; Button button=new Button(计算); Label label1 = new Label(从顶点); Label label2 = new Label(到顶点); Label label3 = new Label(的最短距离是); TextField text1 = new TextField(); TextField text2 = new TextField(); TextField text3 = new TextField();public testpaint()super(Floyd最短路算法：); text3.addActionListener(this); text1.setColumns(0); /设置text1的大小 text2.setColumns(0); /设置text2的大小 text3.setColumns(0); /设置text3的大小 button.addActionListener(this); setLayout(new FlowLayout(); add(label1); add(text1); add(label2); add(text2); add(label3); add(text3); add(button); pack(); setSize(380,266); setVisible(true); int data = /邻接矩阵 0,3,5,8,9999, 3,0,6,4,11, 5,6,0,2,9999, 8,4,2,0,10, 9999,11,9999,10,0,; for (int i = 0; i data.length; i+) for (int j = i; j data.length; j+) if (dataij != dataji) return; Floyd Test=new Floyd(data); for (int i = 0; i data.length; i+) for (int j = i; j datai.length; j+) System.out.println(从顶点+V+(i+1)+到顶点+V+(j+1)+的最短路是:+Test.lengthij); System.out .println();shuzuij=Test.lengthij; public void actionPerformed(ActionEvent e) int a=Integer.parseInt(text1.getText(); int b=Integer.parseInt(text2.getText();text3.setText(String.valueOf(shuzua-1b-1); public void paint(Graphics g) super.paint(g); Graphics2D g1 = (Graphics2D)g; /Ellipse2D.Double /public Ellipse2D.Double(double x,double y,double w,double h) / 根据指定坐标构造和初始化 Ellipse2D 参数： /x - 窗体矩形左上角的 X 坐标,y - 窗体矩形左上角的 Y 坐标,w - 窗体矩形的宽度,h - 窗体矩形的高度 Ellipse2D e1 = new Ellipse2D.Double(40,60 ,20,20); Ellipse2D e2 = new Ellipse2D.Double(200,60,20,20); Ellipse2D e3 = new Ellipse2D.Double(200,200,20,20); Ellipse2D e4 = new Ellipse2D.Double(40,200,20,20); Ellipse2D e5 = new Ellipse2D.Double(320,130,20,20); g1.setPaint(Color.RED); g1.draw(e1); g1.drawString(V1, 45, 75); g1.draw(e2); g1.drawString(V2, 205,75); g1.draw(e3); g1.drawString(V3, 45, 215); g1.draw(e4); g1.drawString(V4, 205, 215); g1.draw(e5); g1.drawString(V5, 325, 145); g1.drawLine(60, 70, 200,70); g1.drawString(3, 130, 70); g1.drawLine(50, 80, 50, 200); g1.drawString(5, 40, 135); g1.drawLine(60, 210,200 ,210); g1.drawString(2, 130,210); g1.drawLine(210, 80, 210,200); g1.drawString(4, 200, 135); g1.drawLine(55, 75, 203, 203); g1.drawString(8, 110, 120); g1.drawLine(55, 203, 203, 75); g1.drawString(6, 85, 170); g1.drawLine(220, 70, 320, 140); g1.drawString(11, 280,110); g1.drawLine(220, 210,320, 140); g1.drawString(10, 280, 160); public static void main(String args) testpaint s=new testpaint(); 3 程序运行结果图 16