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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Floyd 算法 求解 路径 问题 完整 程序代码
链接地址:https://www.31doc.com/p-14123147.html