Floyd算法求解最短路径问题（完整程序代码）
引⾔
在图论中经常会遇到这样的问题，在⼀个有向图⾥求出任意两个节点之间的最短距
离。当节点之间的权值是正值的时候，我们可以采⽤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中每⼀条弧a ij=(v i,v j)
上的权为W(aij)=W
ij，有给定G中的⼀个起点s和重点t，设p是G中从s到t的⼀条路，则定义路径p的权是p中有弧的权之和，记为W（p），即:
W（p）=
(,)
Vi Vj p Wij
∈
∑
⼜若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.2 Floyd的定义与思想
1.2.1 Floyd算法的定义
Floyd算法⼜称为弗洛伊德算法，插点法，是⼀种⽤于寻给定的加权图中顶点间最短路径的算法。
1.2.2 Floyd 算法的思想
利⽤⼀个三重循环产⽣⼀个存储每个结点最短距离的矩阵.弗洛伊德算法仍然使⽤图的邻接矩阵arcs[n+1][n+1]来存储带权有向图。算法的基本思想是：设置⼀个n x n 的矩阵A(k)，其中除对⾓线的元素都等于0外，其它元素a(k)[i][j]表⽰顶点i到顶点j的路径长度，K表⽰运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为∞，当K=0时, A (0)[i][j]=arcs[i][j]，以后逐步尝试在原路径中加⼊其它顶点作为中间顶点，如果增加中间顶点后，得到的路径⽐原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：
第⼀步，让所有边上加⼊中间顶点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-1
D(0) [i][j]是从顶点v
i 到v
j
, 中间顶点是v0的最短路径的长度,
D(k) [i][j]是从顶点v
i 到v
j
, 中间顶点的序号不⼤于k的最短路径长度,
D(n-1)[i][j]是从顶点v
i 到v
j
的最短路径长度。
1.3 Floyd算法描述
通过⼀个图的权值矩阵求出它的每两点间的最短路径矩阵。
a) 初始化：D[u,v]=A[u,v]
b) For k:=1 to n
For i:=1 to n
For j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then
D[I,j]:=D[I,k]+D[k,j];
c) 算法结束：D即为所有点对的最短路径矩阵
从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进⾏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(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.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; i
for(int j=0; j
for(int k=0; k
问题出在我们太早的把i-k-j的距离确定下来了，假设⼀旦到了i-p-j最短的距离后，i到j就相当处理完了，以后不会在改变了，⼀旦以后有使i到j的更短的距离时也不能再去更新了，所以结果⼀定是不对的。所以应当象下⾯⼀样来写程序：
for(int k=0; k
for(int i=0; i
for(int j=0; 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.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 阶⽅阵：
A[i,j]=1 若（Vi,Vj）或者是E(G)中的边；
A[i,j]=0 若（Vi,Vj）或者不是E(G)中的边。
若G是⽹络，则邻接矩阵可定义为：
A[i,j]=Wij 若（Vi,Vj）或属于E（G）
A[I,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）算法过程：１、⽤D[v][w]记录每⼀对顶点的最短距离。
２、依次扫描每⼀个点，并以其为基点再遍历所有每⼀对顶点D[][]的值，看看是否可⽤过该基点让这对顶点间的距离更⼩。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。