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

《Floyd算法求解最短路径问题(完整程序代码).docx》由会员分享，可在线阅读，更多相关《Floyd算法求解最短路径问题(完整程序代码).docx（25页珍藏版）》请在三一文库上搜索。

1、WORD格式整理引言在图论中经常会遇到这样的问题，在一个有向图里求出任意两个节点之间的最短距 离。当节点之间的权值是正值的时候，我们可以采用 Dijkstra算法，用贪心策略加于解 决。但当节点之间的权值有负数的时候，Dijkstra就行不通了，这里介绍另外一种算法 -Floyd最短路径算法。对于任意图，选择存储结构存储图并实现FLOY算法求解最短路经。将问题分解，分解为两方面。一是对于任意图的存储问题，第二个是实现FLOY第法求解最短路经。首先对于图的创建选择合适的存储结构进行存储，对于合适的存储结 构可以简化程序。本实验采用邻接矩阵存储。然后是实现 FLOY算法求解最短路经，在 FLOY算

2、法中路径的长度即是图中两定点间边的权值，FLOY境法要求输出任意两个顶点间的最短路径，而且经过的顶点也要输出。考虑到问题的特殊性，采用一个二维数组和 一个三维数组进行存储。二维数组存储最短路径，三维数组存储路径经过的顶点，在进 行适当的算法后对这两个数组进行输出即可。通过问题的分解，逐个解决，事先所要求 的程序。最短路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等 领域研究的一个热点。传统的最短路径算法主要有 Floyd算法和Dijkstra算法。Floyd算 法用于计算所有结点之间的最短路径。Dijkstra算法则用于计算一个结点到其他所有结 点的最短路径。Dijkstr

3、a算法是已经证明的能得出最短路径的最优解，但它的效率是一 个很大的问题。对于具有n个结点的一个图，计算一个结点到图中其余结点最短路径的 算法时间复杂度为O（n2）。对于一座大中型城市，地理结点数目可能达到几万个到几十 万个，计算最短路径的时间开销将是非常巨大的。本文根据吴一民老师的建议，分析当 前存在的各种求最短路径的算法，提出一种新的基于层次图的最短路径算法，即将一个 平面图划分若干子图，子图抽象为一个高层图。最短路径的计算首先在高层图中进行， 缩小了最短路径的查找范围，降低了最短路径计算的时间开销。由于可以动态计算子图 间的阻抗函数，算法可适用于动态交通诱导系统。设计目的（1）培养学生分析

4、解决问题的能力，掌握java语言的程序设计方法；（2） 通过课程设计实践，训练并提高学生在统筹全局、结构设计、查阅设计资料和计算机编 程方面的能力；（3）提高学生实践论文撰写能力。任务与要求：（1）理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订；(2)课程设计报告(论文)包括要求的作业。第一章Floyd算法1.1 最短路的定义最短路径问题是图论研究中的一个经典算法，旨在寻找图中两结点之间的最短路 径。算法的具体形式包括：确定起点的最短路径问题即已知起始结点，求最短路径问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路经反转的确定

5、起点的问题。确定起点终点的最短路径问题即已知起点和终点求两结点之间的 最短路径。求距离最短路径问题求图中所有的最短路径。用于解决最短路径问题的算法 被称为最短路径算法。单源最短路 定义：给定一个赋权有向图G= (V,E),记G中每一条弧aj =(v i,v j) 上的权为W(aij尸Wij ,有给定G中的一个起点s和重点t ,设p是G中从s到t的一条 路，则定义路径p的权是p中有弧的权之和，记为 W(p),即：W (p) = Z Wij(Vi .Vj)三p又若p*是图G中从s至心的一条路径，且满足W(p*) =minW (p) |p 为 Vs 到 Vt 的路试中对G的所有从s到t的路p取最小，

6、则称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表示运算步骤。开

7、始时，以任意两个顶点之间的有向边的权值作为 路径长度，没有有向边时，路径长度为8,当 K=0时,A (0)ij=arcs皿,以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比 原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：第一步，让所有边上加入中间顶点1,取A皿与Ai1+A1j 中较小的值作Aij的值，完成后得到A”),第二步，让所有边上加入中间顶点2,取A皿与Ai2+A2j中较小的值，完成后得到A2)，如此进行下去，当第n步完成后，得到An), A即为我们所求结 果,Aij表示顶点i到顶点j的最短距离。因此，弗洛伊德算法可以描述为：A

8、(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 -1D (0) ij是从顶点w到vj ,中间顶点是v0的最短路径的长度，D (k) ij是从顶点vi到w ,中间顶点的序号不大于k的最短路径长度，D (n-1) ij是从顶点w到vj的最短路径长度。1.3 Fl

9、oyd 算法描述通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。a)初始化：Du,v=Au,vb) For k:=1 to nFor i:=1 to nFor j:=1 to nIf Di,jDi,k+Dk,j ThenDI,j:=DI,k+Dk,j;c)算法结束：D即为所有点对的最短路径矩阵从图的带权邻接矩阵A=a(i,j) nxn开始，递归地进行n次更新，即由D(n-1)构造出矩阵 D(n)。矩阵D(n)的iD(2)；矩阵D(0)=A,按一个公式，构造出矩阵D(1);又用同样地公式由D(1)构造出;最后又用同样的公式由行j列元素便是i号顶点到j号顶点的最短路径长度，称 D(n)为图的距

10、离矩 阵，同 还可引入一个后继节点矩阵path来记录两点间的最短路径。采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为 0mA3);其状态转移方程如下：mapi,j:=minmapi,k+mapk,j,mapi,jmapi,j表示 i 至U j 的最短距离 K是穷举i,j的断点mapn,n初值应该为0,或者按照题目意思来做。当然,如果这条路没有通的话，还必须特殊处理，比如没有mapi,k这条路1.4 Floyd算法过程在图论中经常会遇到这样的问题，在一个有向图里，求出任意两个节点之间的最短距离。我们在离散数学、数据结构课上都遇到过这个问题，在计算机网络里介绍网络层的时

11、候好像也遇到过这个问题，记不请了 但是书本上一律采取 的是Dijkstra 算法，通过 Dijkstra算法可以求出单源最短路径，然后逐个节点利用Dijkstra算法就可以了。不过在这里想换换口味，采取 Robert Floyd 提出的算法来解决这个问题。下面让我们先把问题稍微的形式化一下：如果有一个矩阵D=d(ij),其中d(ij)0 表示i城市到j城市的距离。若i与j之间无路可通，那么 d(ij)就是无穷大。又有 d(ii)=0 o编写一个程序，通过 这个距离矩阵 D,把任意两个城市之间的最短与其行径的路径找出来。我们可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何

12、找出最短路径呢，这里还是用到动态规划的知识，对于任何一个城市而言，i至M的最短距离不外乎存在经过 i与j之间的k和不经过k两种可能，所以 可以令k=1, 2, 3, . , n(n是城市的数目)，在检查d(ij)与d(ik)+d(kj) 的值; 在此d(ik)与d(kj)分别是目前为止所知道的 i至U k与k到j的最短距离，因此d(ik)+d(kj) 就是i到j经过k的最短距离。所以，若有 d(ij)d(ik)+d(kj) ,就表示从i出发经过k再到j的距离要比原来的i至Uj距离短，自然把i到j的d(ij)重写为d(ik)+d(kj),每当一个k查完了，d(ij)就是目前的i到j的最短距离。重

13、复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i至ij 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的更短的距离时也不能再去更新了，所以结果一定是不对的。所以应当象下面一样来写程序：

14、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 =

15、 min( Gi,j, Gi,k+Gk,j),如果 Gi,j的值变小,则 Di,j=k 。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从 V5至I 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) ,是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密

16、图，效率要高于执行|V|次DijkStra 算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点：时间复杂度比较高，不适合计算大量数据。第二章邻接矩阵2.1 邻接矩阵的定义邻接矩阵(Adjacency Matrix ):是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V=v1,v2,vn。G的邻接矩阵是一个具有下列性质的n阶方阵：2.2 邻接矩阵的特点无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上(下)三角阵中剔除了左上右下对角线上的0元

17、素后剩余的元素，故只需 1+2+.+(n-1)=n(n-1)/2个单元。无向图邻接矩阵的第 i行(或第i歹I)非零元素的个数正好是第 i个顶点的度。 有向图邻接矩阵中第 i行非零元素的个数为第 i个顶点的出度，第i列非零元素 的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之 和。用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。2.3 3邻接矩阵的表示方法2.3.1 图的邻接矩阵表示法在图的邻接矩阵表示法中：用邻接矩阵表示顶点间的相邻关系用一个顺序表来存储顶点信息2.3.2 图的邻接矩阵(Adacency Matrix)设G=(V, E)是具有n个顶点的图，则 G

18、的邻接矩阵是具有如下性质的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或00 若(Vi,Vj )或 不属于 E (G)其中：Wij表示边上的权值;8表示一个计算机允许的、大于所有边上权值的数。【例】下面带权图的两种邻接矩阵分别为 A 3和A 4。A3=专业资料值得拥有2.3.3 邻接矩阵的特点:无向图的邻接矩阵一定是一个对称矩阵无向图的邻接矩阵的第i行（或第i列）非零元素（或非无穷元素）个数为第i个顶点的度 D （v

19、i）.有向图的邻接矩阵的第i行非零元素（或非无穷元素）个数为第 i个顶点的度OD（vi）,第i列非零元素（或非无穷元素）个数就是第 i个顶点的入度ID （vi）。邻接矩阵表示图,很容易确定图中任意两个顶点之间是否有边相连。容易判断两个顶点之间是否有 长度为m的路径相连。邻接矩阵表示法的缺点：邻接矩阵占用的存储单元个数只与图中的结点个数有关，而与边的数目无关。一个n各节点的图，若其边数比n平方少得多，那么邻接矩阵中存在大量的无用的单元。第三章Floyd算法实例3.1 Floyd算法实例 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表城市之间的距离。求每个城市的最

20、短距离【输入】 用V表示各个城市，输入顶点 Vi与Vj ,输入样例输出样例输入样例输出样例输入样例输出样例1 102 203 421 232 363 5121 352 444 401 472 5114 5101 5143 305 50【输出】 输出所有可能连接的城市的最短距离最短路径算法的作用就是在图中找出任意两点间最短距离的途径，比如可以在地图 上找出任两个城市之间路程最短的那条路径。有两种算法可以实现，一种是迪杰斯特拉（Dijkstra ）算法，一种是弗洛伊德（Floyd）算法。弗洛伊德（Floyd）算法过程：1、用Dvw记录每一对顶点的最短距离。2、依次扫描每一个点，并以其为基点再遍历所

21、有每一对顶点D叩的值，看看是否可用过该基点让这对顶点间的距离更小。算法理解：最短距离有三种情况：1、两点的直达距离最短。（如下图v,x）2、两点间只通过一个中间点而距离最短。（图v,u）3、两点间用通过两各以上的顶点而距离最短。（图）对于第一种情况：在初始化的时候就已经找出来了且以后也不会更改到。对于第二种情 况：弗洛伊德算法的基本操作就是对于每一对顶点，遍历所有其它顶点，看看可否通过 这一个顶点让这对顶点距离更短，也就是遍历了图中所有的三角形（算法中对同一个三 角形扫描了九次，原则上只用扫描三次即可，但要加入判断，效率更低）。对于第三种情况：如下图的五边形，可先找一点（比如 x,使=2）,就

22、变成了四边形问题，再 找一点（比如y, =2）,可变成三角形问题了（ v,u,w）,也就变成第二种情况了， 由此对于n边形也可以一步步转化成四边形三角形问题。（这里面不用担心哪个点要先 找哪个点要后找，因为找了任一个点都可以使其变成（n-1）边形的问题）。第四章结论通过Floyd算法求解图中顶点的最短路径问题实验， 更加深入的了解了数据结构与 算法在各个领域的应用。比如图的最短路径问题，衍生为校内导游图，乘客路径问题等 等的实际性的日常问题。在该实验的求解过程中，把问题分解为三个部分来解决。首先考虑的是对于任意图 的存储问题。在数据结构与算法中，介绍了多种图的存储结构，有邻接矩阵存储，邻接 表

23、存储以及十字链表等等存储方法。考虑到本实验要对图进行求解路径，采用邻接矩阵 存储。邻接矩阵存储图很容易判断图中两个顶点是否相连。例如，判断 Vi和Vj是否相 连，只需检查Gij是否等于零，如果该、等于零则不相连。以上是两个顶点是否直 接相连的算法。然后是路径问题，对于任意两个顶点，路径也就分为三个情况，即直接相连是最短 路径，经过某几个顶点后，经过的路径是最短路径，还有这两个顶点之间没有最短路径。 对于直接相连的路径就是最短路径，直接输出即可。例如ab直接相连，且最短路径就是直接路径，路径长度为10,输出a到b的路径就为：a-b,路径长度为10。经过 某几个定点后的路径是最短路径，用二维数组l

24、ength叩先保存最短路径长。若lengthijlengthik+lengthkj则经过k点后i至打得的路径短一些，此时将lengthik+lengthkj 赋值给 lengthij ,用二维数组path记录下经过的点k,这样在循环里对整个路径都进行一 边比较，保存下最短路径以及这些路径经过的顶点。对于两点之间没有路径的问题， lengthij一直为最大值，若有路径则同第二步，没有则lengthij一直保持不变。最后待解决的问题就是输出任意两点之间的最短路径，从i至” 的最短路径全部保存在length叩中，要向输出任意两点之间的最短路径长度并不难，但如何输出之间经历过的定点呢？在存入的时彳8首

25、先存入p是离j最近的一点，然后是离p最近的一点， 依次存入，最后一个存入的是离i最近的顶点，所以输出的时候必须倒序输出。采用向 前递归算法实现。在 3x3循环里，如果lengthij=0 或者lengthij=INF （INF 是自定义的最大值）都是没有路径的，lengthij=0 此时若i=j ,则是定点无路径。 若lengthij=INF 则i至U j没有路径。如果lengthij=0 但是i!=j ,此时说明i 到j的最短路径是0,路径是存在的，应该另外考虑这种情况，同下面的输出一致。若 以上三种情况都不符合则执行正常的输出操作，输出从i至叮经过的顶点，并输出路径长度。通过上述三个步骤，

26、解决了 Floyd算法的最短路径问题参考文献1朱福喜编著.面向对象与Java程序设计.北京：清华大学出版社，20082焦永兰主编.管理运筹学.北京：中国铁道出版社，20023黄国瑜，叶乃菁编著。数据结构。清华大学出版社， 200520044朱福喜，唐晓军编著.Java编程技巧与开发实例.北京：清华大学出版生，5王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2006.56侯风巍，杨永田.数据结构要点精细.北京航空航天大学出版社，2006.8附录1程序流程图:N流程图程序实现代码:package Example;import java.awt.*;import java.awt.event.

27、*;importjava.awt.geom.Ellipse2D;importpublicintmax =9999;introw = G.length ;/intint叩A =口Path =new int rowrow;lengthnew int row;new int rowrow;/图G勺行数/定义任意两点之间经过的点 记录一条路径for ( int i = 0; i row; i+)/处理图两点之间的路径for ( int j = 0; j row; j+) if (G皿=0)Gij = max;/没有路径的两个点之间的路径为默认最大if (i = j) Gij = 0;/本身的路径长度为

28、0for ( int i = 0; i row; i+)for ( int j = 0; j row; j+)A皿=-1;for ( int i = 0; i row; i+)/初始化为任意两点之间没有路径Pathi = -1;/假设任意两点之间的没有路径javax.swing.*;class testpaint extends JFrame implements ActionListener int length = null ;public void Floyd( int G) for ( int m = 0; m row; +m) for ( int n = 0; n row; +n)

29、length mn = Gmn;for ( int u = 0; u row; +u)for ( int m = 0; m row; +m)for ( int n = 0; n length mu + length un) length mn = length mu + length un;/ 如果存在更短路径则取更短路径Amn = u;/ 把经过的点加入for ( int i = 0; i row; i+) /求出所有的路径int 口 point = new int 1;for ( int j = 0; j row; j+) point0 = 0;Pathpoint0+ = i;output

30、Path(A, i, j, Path, point); void outputPath( int 口口A,int i, int j, int 口Path,int 口 point) /输出i到j的路径的实际代码，point口记录一条路径的长度if (i = j)return ;if (A皿=-1)Pathpoint0+ = j;else outputPath(A, i, Aij, Path, point);outputPath(A, Aij, j, Path, point);int shuzu = new int 66;Buttonbutton=new Button(”计算);Labellabe

31、l1=new Label(“从顶点);Labellabel2=new Label(到顶点);Labellabel3=new Label(”的最短距离是TextFieldtext1 =new TextField(TextFieldtext2 =new TextField(TextFieldtext3 =new TextField(publictestpaint()super (Floyd最短路算法：);this );text3.addActionListener(text1.setColumns(0);/设置text1的大小text2.setColumns(0);/设置text2的大小text3

32、.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,

33、;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 从顶点军工到顶点V1的最短路是：0 从顶点vl到顶点的路径是：1一2一 从顶点U1到顶点V2的最短路是:3从顶点VI到顶点E3的路径是：13一从顶点U1到顶点U3的最短路是:5从顶点丫工到顶点U4的路径是：12一4从顶点UI到

34、顶点V4的最短路是:7从顶点可1到顶点的路径是：125从顶点VI到顶点V5的最短路是:14 从顶点2到顶点位的路径是：2下 从顶点V2到顶点V2的最短路是：0 从顶点炉2到顶点v3的路径是：23 从顶点V2到顶点V3的最短路是：6从顶点v2到顶点u4的路径是:24 从顶点Y2到顶点V*的最短路是：4从顶点狭2到顶点uS的路役是:25 从顶点V2到顶点V5的最短路是：11 从顶点v3到顶点的路径是：3 从顶点V3到顶点M3的最短路是:0从顶点V3到顶点VT的路径是：3可一 从顶点U3到顶点V4的最理路是:2从顶点V3到顶点U5的路径是：3印一5 从顶点N3到顶点V5的最短路是:12从顶点V4到顶点4的路径是：4 从顶点U4到顶点U4的最短路是:0 从顶点Y4到顶点Y5的路径是：45一 从顶点U4到顶点V5的最短路是:10 从顶点寸5到顶点寸5的路径是：5从顶点US到顶点V5的最短路是：