下载文档原格式
Floyd算法（各对顶点之间的最短距离）Floyd算法（各对顶点之间的最短距离）在上篇文章中议论到了如何求算单源最短路径，因此要想求各对顶点之间的距离，只需循环求算n次即可。
还有另外一种办法来求算各对顶点之间的最短距离，就是Floyd算法，因为其算法过程比Dijksa更简单理解，并且代码更简洁，因此当求算各对顶点之间的最短距离常采纳Floyd算法。
一.Floyd算法假设从i到j的最短路径上要经过若干个顶点，这些中间顶点中最大的顶点编号为k，最小的顶点为t，因此要求算dist[i][j]的最小值，那么只需要求算dist[i][s]+dist[s][j](t =s =k)的全部值，并取其中最小者即可。
因此可以设置一个中间顶点k(0 =k n)分离插入到每队顶点(i,j)之中，并更新dist[i][j]的值。
当n个顶点插入到每队顶点之中，求解便结束了。
其实Floyd算法实质上是一个动态规划算法。
代码实现: /*每对顶点之间最短路径Floyd 2011.8.27*/ iludeiostream include stack define M 100define N 100using namespace std;typef struct node{ int matrix[N][M]; //邻接矩阵 int n; //顶点数 int e; //边数 }MGraph; vo FloydPath(MGraph g,intdist[N][M],int path[N][M]){ int i,j,k; for(i=0;i g.n;i++)for(j=0;j g.n;j++) { if(g.matrix[i][j] 0){ dist[i][j]=g.matrix[i][j]; path[i][j]=i; } ee { if(i!=j) { dist[i][j]=INT_MAX; path[i][j]=-1; } else { dist[i][j]=0; path[i][j]=i; } } } for(k=0;k g.n;k++) //中间插入点(注重理解k为什么只能在最外层) for(i=0;i g.n;i++) for(j=0;jg.n;j++) { if((dist[i][k] 0 dist[i][k] INT_MAX) //防止加法溢出 (dist[k][j] 0 dist[k][j] INT_MAX) dist[i][k]+dist[k][j] dist[i][j]) { dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=path[k][j]; //path[i][j]记录从i到j的最短路径上j 的前一个顶点 } } }void showPath(int path[N][M],int s,int t) //打印出最短路径 { stack int st; int v=t; while(t!=s) { st.push(t);第1页共2页。
Floyd算法Floyd算法是一种经典的图论算法，用于求解带权有向图中任意两个顶点之间的最短路径问题。
该算法由美国数学家罗伯特·弗洛伊德（Robert Floyd）于1962年提出，因此得名为Floyd算法。
Floyd算法是一种动态规划算法，它采用了“分治”的思想，将问题分解为更小的子问题，然后逐步解决子问题，最终得到解决整个问题的结果。
本文将从算法的背景、基本思想、实现方法及优缺点等方面对Floyd 算法进行详细阐述和分析。
一、算法的背景在讲Floyd算法之前，我们先来了解一下最短路径问题。
顾名思义，最短路径问题就是在给定图中找到两个给定节点之间的一条最短路径，也就是路径上各边权值之和最小的路径。
这个问题在现实生活中有很多应用，比如网络路由、地图路径规划、航线安排等等。
在数学和计算机科学领域中，我们可以通过图论的方法来描述和解决这个问题。
一般来说，给定一张带权有向图G=(V, E)，其中V表示节点的集合，E表示边的集合。
每条边E(i,j)的权重为w(i,j)，表示从节点i到节点j的距离或成本。
那么最短路径问题就是在图中找到从节点s到节点t的一条最短路径P，并且P上的边权之和最小。
最初求解的思路是按照类似深度优先搜索的方式，逐个遍历所有路径，然后依次比较它们的距离，找到最短路径。
但这种方式显然是不可行的，因为它的时间复杂度非常高。
所以，我们需要设计一种更高效的算法，以求得最短路径问题的最优解。
二、算法的基本思想Floyd算法就是一种高效地解决最短路径问题的方法。
它采用了“动态规划”的思想，通过逐步求解子问题，最终得到完整的最短路径。
而解决子问题的方式则是采用了“分治”的思想，将问题分解为更小的子问题，然后逐步解决。
具体地说，Floyd算法采用了“中转节点”的概念，我们可以将问题转化为这样一个子问题：对于每个节点i和节点j，假设我们已经知道了它们之间的最短路径长度为d[i][j]，那么考虑一下节点k作为中转节点，它可以为i和j之间的路径P提供一个“中转服务”，将P拆分为两条路径：i-->k和k-->j。
文章编号：001主题：探讨floyd算法求解邻接矩阵的最短距离矩阵在计算机算法中，图论一直是一个重要的研究领域。
而其中，最短路径算法一直是图论中的热门话题之一。
在众多的最短路径算法中，floyd算法因其简洁高效的特点而备受青睐。
本文将深入探讨floyd算法在求解邻接矩阵的最短距离矩阵中的应用，并分析其实现原理及优缺点。
一、floyd算法简介Floyd算法是一种用于寻找加权图中顶点之间最短路径的动态规划算法。
它的基本思想是每次引入一个新的顶点，看看这个新顶点能不能对原来两个顶点之间的距离产生改变，如果可能，就进行更新。
通过多次迭代，最终得到所有顶点之间的最短路径。
二、floyd算法的实现步骤1. 初始化邻接矩阵在使用floyd算法求解最短路径时，首先需要初始化邻接矩阵。
邻接矩阵的每个元素代表图中两个顶点之间的距禋，如果两个顶点之间没有直接连接，则距离设为无穷大。
如果两个顶点直接相连，则距离设为两个顶点之间的权值。
2. 动态规划求解最短路径接下来，利用动态规划的思想，通过逐渐引入新的顶点，不断更新已有的最短路径。
具体做法是，对于每对顶点i和j，检查它们之间是否存在顶点k，使得从i到j的最短路径可以经过顶点k。
如果存在这样的顶点k，那么更新i到j的最短路径为i到k和k到j的距离之间的较小值。
3. 递推过程重复上述步骤，通过逐渐引入新的顶点k，直到遍历完所有顶点，就可以得到最终的最短距离矩阵。
三、floyd算法的优缺点1. 优点floyd算法可以求解任意两点之间的最短路径，且适用于有向图和无向图。
并且可以方便地求出最短路径的具体路径。
算法简单易懂，实现起来也比较容易。
2. 缺点floyd算法的时间复杂度较高，为O(n^3)，当n较大时，计算量会非常庞大。
另外，在处理稀疏图时，可能会造成大量的计算浪费，因为floyd算法会对所有的顶点对进行遍历，而对于稀疏图来说，很多顶点对之间并不存在直接连接的边。
四、个人观点和理解在实际应用中，floyd算法通常适用于节点数量不是特别大，但边的数量非常大或者需要求解任意两点之间最短路径的情况。
求最短路径算法总结分类：数据结构标签：floyd算法it部分内容参考All-Pairs 的最短路径问题:所有点对之间的最短路径Dijkstra算法是求单源最短路径的，那如果求图中所有点对的最短路径的话则有以下两种解法：解法一：以图中的每个顶点作为源点，调用Dijkstra算法，时间复杂度为O(n3)；解法二：Floyd（弗洛伊德算法）更简洁，算法复杂度仍为O(n3)。
n正如大多数教材中所讲到的，求单源点无负边最短路径用Dijkstra，而求所有点最短路径用Floyd。
确实，我们将用到Floyd算法，但是，并不是说所有情况下Floyd都是最佳选择。
对于没有学过Floyd的人来说，在掌握了Dijkstra之后遇到All-Pairs最短路径问题的第一反应可能会是：计算所有点的单源点最短路径，不就可以得到所有点的最短路径了吗。
简单得描述一下算法就是执行n次Dijkstra算法。
Floyd可以说是Warshall算法的扩展了，三个for循环便可以解决一个复杂的问题，应该说是十分经典的。
从它的三层循环可以看出，它的复杂度是n3，除了在第二层for中加点判断可以略微提高效率，几乎没有其他办法再减少它的复杂度。
比较两种算法，不难得出以下的结论：对于稀疏的图，采用n次Dijkstra比较出色，对于茂密的图，可以使用Floyd算法。
另外，Floyd可以处理带负边的图。
下面对Floyd算法进行介绍：Floyd算法的基本思想：可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。
如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个城市而言，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的最短距离。
Floyd算法详解Floyd-WarshallFloyd算法，是⼀种著名的多源最短路算法。
核⼼思想：⽤邻接矩阵存储图，核⼼代码为三重循环，第⼀层枚举中间点k，⼆三层分别枚举起始点i与⽬标点j。
然后判断经过中间点k后，i与j间的路程是否会减⼩。
如果是，就更新i，j之间的最短路。
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j];需要注意的是，为了保证更新成功，需要将e数组初始化为⽆穷⼤。
同时为了防⽌程序做⽆意义的到⾃⼰的最短路，将每个节点到本⾝的距离初始化为0。
算法复杂度：该算法的空间复杂度为n^2(不算优秀，但勉强接受),时间复杂度O(n^3)（呵呵）。
完整代码：#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int inf=99999999;int n,m,x,y,z,s;int dis[1001][1001];int main(){scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j) dis[i][j]=inf;else dis[i][j]=0;for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);dis[x][y]=dis[y][x]=z;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(dis[i][k]+dis[k][j]<dis[i][j])dis[i][j]=dis[i][k]+dis[k][j];for(int i=1;i<=n;i++)printf("%d ",dis[s][i]);return0;}算法优化：for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= i; j++)dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]),dis[j][i] = dis[i][j];这⾥利⽤了矩阵的对称性，只更新⼀半矩阵即可。
【最短路径Floyd 算法详解推导过程】看完这篇，你还能不懂Floyd 算法？还不会？简介Floyd-Warshall 算法（Floyd-Warshall algorithm ），是⼀种利⽤动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra 算法类似。
该算法名称以创始⼈之⼀、1978年图灵奖获得者、简单的说就是解决任意两点间的最短路径的⼀种算法，可以正确处理有向图或负权的最短路径问题，同时也被⽤于计算有向图的传递闭包。
Floyd-Warshall 算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
解决最短路径问题有⼏个出名的算法:1.dijkstra 算法,最经典的单源最短路径算法2.bellman-ford 算法,允许负权边的单源最短路径算法3.spfa,其实是bellman-ford+队列优化,其实和bfs 的关系更密⼀点4.floyd 算法,经典的多源最短路径算法今天先说说FloydFloyd 算法详解描述a ）如图：存在【0,1,2,3】 4个点，两点之间的距离就是边上的数字，如果两点之间，没有边相连，则⽆法到达，为⽆穷⼤。
b ）要让任意两点（例如从顶点a 点到顶点b ）之间的路程变短，只能引⼊第三个点（顶点k ），并通过这个顶点k 中转即a->k->b ，才可能缩短原来从顶点a 点到顶点b 的路程。
那么这个中转的顶点k 是0~n中的哪个点呢？算法过程准备1）如图 0->1距离为5，0->2不可达，距离为∞，0->3距离为7……依次可将图转化为邻接矩阵（主对⾓线，也就是⾃⾝到⾃⾝，我们规定距离为0，不可达为⽆穷⼤），如图矩阵⽤于存放任意⼀对顶点之间的最短路径权值。
2）再创建⼀个⼆维数组Path 路径数组，⽤于存放任意⼀对顶点之间的最短路径。
每个单元格的内容表⽰从i 点到j 点途经的顶点。
（初始还未开始查找，默认-1）开始查找1）列举所有的路径（⾃⼰到⾃⼰不算）即为：0 -> 1 , 0 -> 2 , 0 -> 3 ,1 -> 0 , 1 ->2 , 1 ->3 ,2 -> 0 , 1 -> 1 , 1 -> 3######转化成⼆元数组即为：{0，1}，{0，2}，{0，3}，{1，0}，{1，2}，{1，3}，{2，0}，{2，1}，{2，3}，{3，0}，{3，1}，{3，2}2）选择编号为0的点为中间点{0，1}，{0，2}，{0，3}，{1，0}，{1，2}，{1，3}，{2，0}，{2，1}，{2，3}，{3，0}，{3，1}，{3，2}从上⾯中⼆元组集合的第⼀个元素开始，循环执⾏以下过程：1. ⽤i，j两个变量分别指向⼆元组⾥的两个元素，⽐如{0，1}这个⼆元组，i指向0；j指向12. 判断 (A[ i ][ 0 ]+A[ 0 ][ j ] ) < A[ i ][ j ] （即判断 i -> j，i点到j点的距离是否⼩于从0点中转的距离），如果false，则判断下⼀组⼆元数组。
Floyed（floyd）算法详解是真懂还是假懂？Floyed算法：是最短路径算法可以说是最慢的⼀个。
原理：O（n^3）的for循环，对每⼀个中间节点k做松弛（寻找更短路径）；但它适合算多源最短路径，即任意两点间的距离。
但spfa，迪杰斯特拉就只能算⼀个点到其他任⼀点的最短路径。
关键在于，我们真的真正理解floyed吗？就是因为它太短了，以⾄于我们有些⼈（神仙除外）看代码后看到这样⼀个语句：d[i][j]=min(d[i][j],d[i][k]+d[k][j])也就是说，对于每⼀个中转点k来说，进⾏O（n^2）的松弛，⼀定能找到最短路径。
虽不是最优，但是松弛次数来凑！这⼤概就是我们（之前的我）的⽆须证明的，想当然的理解，并背下来了它，以便以后想TLE时⽤。
（O（n^3））；so？Floyed本质是dp；递推公式：（图⽚源⾃⽹络⼤佬）众所周知，dp（动态规划）要满⾜⽆后效性。
也就是说。
还是先举个例⼦：我们设k取某⼀个k1时满⾜k1为最终点i到j最短路经过的点，但是在外层循环到k1时d[i][k1]和d[k1][j]并没有取到最⼩值，因为k1只能取⼀次，那么往后再循环是不是就取不到k1了呢？？答案当然不是的（不然这个算法为什么正确?）还是那句话，dp⽆后效性，也就是说，k不单单是枚举，还是⼀个状态变量，找i和j之间通过编号不超过k（k从1到n）的节点的最短路径（⼀定要注意，这⾥是当前最短路径，k之前的已经变成最短路了,对于每⼀个k，我们都进⾏了n^2的充分枚举(ij)，已保证当前已经满⾜对从1到k的节点最优，那么当k枚举完所有点，那么⼀定是最优的了换句话说，在d[i][j]=min(d[i][j],d[i][k]+d[k][j])公式中，因为k之前已经作为i或者j被枚举过了；,d[i][k]和d[k][j]已经被1到k枚举过了那么他们⼀定是1到k节点中最优的路径，等枚举到n时，所有的都枚举完了，那么它们就是基本代码:for(k=1;k<=n;k++) //中转节点for(i=1;i<=n;i++) 第⼆层循环for(j=1;j<=n;j++) 第三层循环if(e[i][j]>e[i][k]+e[k][j] )如果直接到达⽐通过k这个中转接点到达的距离短e[i][j]=e[i][k]+e[k][j];那么就更新松弛算法复杂度O（n^3），这也是为什么平常很少使⽤的原因。
