floyd算法（Floyd算法是什么）

本文目录

• Floyd算法是什么
• Floyd算法的优缺点分析
• 怎么根据Floyd算法 从多个顶点中选出几个，使其他点到选出点距离最短
• 最短路的Floyd算法有些不明白的地方，请求大神支援
• floyd-warshanll算法是什么啊
• 比较Dijkstra算法与Floyd算法
• 最短路径的floyd算法的时间复杂度
• floyd判圈算法
• floyd算法 是动态规划的思想吗
• floyd算法的三重循环问题

Floyd算法是什么

Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 　　从图的带权邻接矩阵A= 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初值应该为0，或者按照题目意思来做。 　　当然，如果这条路没有通的话，还必须特殊处理，比如没有map这条路

Floyd算法的优缺点分析

Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法，也要高于执行V次SPFA算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。缺点：时间复杂度比较高，不适合计算大量数据。

怎么根据Floyd算法 从多个顶点中选出几个，使其他点到选出点距离最短

先用floyd求出距离矩阵D，即以下代码中的矩阵B。以下matlab程序为从12个点中选出3点，可以此类推。clear all;A=; %列出12个居民点选3个缴费点的所有情况。for i=1:nchoosek(12,3) %for……end， 循环，计算以上列出所有情况下所有居民需要行走的总路程！A2=A(i,:); A3=A2(1,1); %读取选取3个居民点A4=A2(1,2);A5=A2(1,3); People=; %每个居民点的人数的矩阵。B=; %居民到其他居民点所有最短的距离。 B1=B(:,A3); %居民点到所选的缴费点的理论最短距离。B2=B(:,A4);B3=B(:,A5); C=; D=sort(C,2); Shortjourney=D(:,1); %每位居民选择缴费点后需要行走的最短路程。 Sum(i)=People*Shortjourney; %所有居民所要行走的路程总和。end E=; %将以上得到的数组转为矩阵。 minposition=find(E==min(E)); %找出最小值在矩阵的位置。A=; %A的顺序与E的一致！position=A(minposition,:) %最佳的缴费点的选择。

最短路的Floyd算法有些不明白的地方，请求大神支援

floyd算法本质是动态规划，可以写成三维来理解f那么我们依次的扩大k，当k从1扩大到n，最终的答案也就得出考虑如何从从k推到k+1。首先，最短路不可能经过k+1号点两次，所以一条包含k+1号点的最短路必然是由一段只包含1~k的点的路径P1+(k+1号点)+另一端只包含1~k的点的路径P2得出的，枚举起点i和终点j，拼接得的长度为f仔细观察后又会发现，将第一维拿掉丝毫不影响答案，将第一维删除后，就得到了用两维数组存储的floyd算法。

floyd-warshanll算法是什么啊

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。 　　　Floyd-Warshall算法的描述如下： 　　for k:=1 to n do for i:=1 to n do for j:=1 to n do if dist; 　　Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。 　　注意单独一条边的路径也不一定是最佳路径。 　　从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。 　　对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。 　　不可思议的是，只要按排适当，就能得到结果。 　　// dist(i,j) 为从节点i到节点j的最短距离 　　For i←1 to n do 　　For j←1 to n do 　　dist(i,j) = weight(i,j) 　　For k←1 to n do // k为“媒介节点” 　　For i←1 to n do 　　For j←1 to n do 　　if (dist(i,k) + dist(k,j) 《 dist(i,j)) then // 是否是更短的路径？ 　　dist(i,j) = dist(i,k) + dist(k,j) 　　这个算法的效率是O(V^3)。它需要邻接矩阵来储存图。 　　这个算法很容易实现，只要几行。 　　即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许(只要有放的下邻接矩阵的空间，时间上就没问题)。 　　计算每一对顶点间的最短路径（floyd算法） 　　【例题】设计公共汽车线路(1) 　　现有一张城市地图，图中的顶点为城市，有向边代表两个城市间的连通关系，边上的权即为距离。现在的问题是，为每一对可达的城市间设计一条公共汽车线路，要求线路的长度在所有可能的方案里是最短的。 　　输入： 　　n (城市数，1≤n≤20) 　　e (有向边数1≤e≤210) 以下e行，每行为边（i,j）和该边的距离wij（1≤i,j≤n） 　　输出： 　　k行，每行为一条公共汽车线路 　　分析：本题给出了一个带权有向图，要求计算每一对顶点间的最短路径。这个问题虽然不是图的连通性问题，但是也可以借鉴计算传递闭包的思想：在枚举途径某中间顶点k的任两个顶点对i和j时，将顶点i和顶点j中间加入顶点k后是否连通的判断，改为顶点i途径顶点k至顶点j的路径是否为顶点i至顶点j的最短路径（1≤i，j，k≤n）。 显然三重循环即可计算出任一对顶点间的最短路径。设 n—有向图的结点个数； path—最短路径集合。其中path为vi至vj的最短路上vj的前趋结点序号(1≤i，j≤n)； adj—最短路径矩阵。初始时为有向图的相邻矩阵 　　我们用类似传递闭包的计算方法反复对adj矩阵进行运算，最后使得adj成为存储每一对顶点间的最短路径的矩阵 　　(1≤i，j≤n) 　　Var 　　adj：array of 0‥n； 　　计算每一对顶点间最短路径的方法如下： 　　首先枚举路径上的每一个中间顶点k（1≤k≤n）；然后枚举每一个顶点对（顶点i和顶点j，1≤i，j≤n）。如果i顶点和j顶点间有一条途径顶点k的路径，且该路径长度在目前i顶点和j顶点间的所有条途径中最短，则该方案记入adj adj矩阵的每一个元素初始化为∞； 　　for i←1 to n do {初始时adj为有向图的相邻矩阵，path存储边信息} 　　for j←1 to n do if wij《》0 then 　　begin 　　adj《》0 {若顶点i可达顶点j，则输出最短路径方案} 　　then begin 　　print（i，j）； 　　writeln； 　　end；{then}

比较Dijkstra算法与Floyd算法

（1）Dijkstra算法：在网络中用得多，一个一个节点添加，加一个点刷一次路由表。

Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

（2）Floyd算法：把所有已经连接的路径都标出来，再通过不等式比较来更改路径。

Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

最短路径的floyd算法的时间复杂度

Floyd：每对节点之间的最短路径。Floyd-Warshall算法（Floyd-Warshall    algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。

Dijkstra： O(n2) 适用于 权值为非负 的图的单源最短路径，用斐波那契堆的复杂度O(E+VlgV)，

BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度O(VE)

SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度O(kE)，k为每个节点进入Queue的次数，且k一般《=2，但此处的复杂度证明是有问题的，其实SPFA的最坏情况应该是O(VE).

先给出结论：

(1)当权值为非负时，用Dijkstra。

(2)当权值有负值，且没有负圈，则用SPFA，SPFA能检测负圈，但是不能输出负圈。

(3)当权值有负值，而且可能存在负圈，则用BellmanFord，能够检测并输出负圈。

(4)SPFA检测负环：当存在一个点入队大于等于V次，则有负环，后面有证明。

floyd判圈算法

问题：如何检测一个链表是否有环，如果有，那么如何确定环的起点. 要求 : 空间复杂度为O(1), 时间复杂度为O(n).

假设一个有环链表如下图: 利用floyd判圈算法可以做到下面的三件事:

使用两个指针slow和fast。两个指针都从链表的起始处S开始。slow每次向后移动一步，fast每次向后移动两步。若在fast到达链表尾部前slow与fast相遇了，就说明链表有环。 这里可以简单的证明一下：反证法，假如没有环，那么slow永远追不上fast，那么在fast到达链表尾部前slow不会fast相遇了。若相遇了，链表就有环。

当slow和fast相遇时，slow和fast必定在环上，所以只要让一者不动，另一者走一圈直到相遇，走过的节点数就是环的长度。

如图所示，设AB=n, SA=m。设环的长度为L。 假设slow走过的节点数为i，那么有： i = m + n + a L a为slow绕过的环的圈数。 因为fast速度为slow的两倍，所以相同时间走过的节点数为slow的两倍，所以有： 2 i = m + n + b L b为fast绕过的环的圈数。 两者做差有 : i = (b-a) L。 所以可知，fast和slow走过的距离是环的整数倍。 所以有m+n=L。 所以此时让slow回到起点S，，fast仍然在B。 让两个指针以每次一步的速度往前走。 当走了m步时，可发现slow和fast正好都在A处，即是环的起点。

floyd判圈算法是一个很有趣的算法，在某些题目上用处很大，比如下面这个。

给出一个数组 nums 包含 n + 1 个整数，每个整数是从 1 到 n (包括边界)，保证至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。 注意事项

对于这个题目

floyd算法 是动态规划的思想吗

1.定义概览Floyd-Warshall算法（Floyd-Warshallalgorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。2.算法描述1)算法思想原理：Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k)+Dis(k,j)《Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j)=Dis(i,k)+Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。2).算法描述：a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。　　b.对于每一对顶...1.定义概览Floyd-Warshall算法（Floyd-Warshallalgorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。2.算法描述1)算法思想原理：Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k)+Dis(k,j)《Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j)=Dis(i,k)+Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。2).算法描述：a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。　　b.对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果是更新它。3).Floyd算法过程矩阵的计算----十字交叉法方法：两条线，从左上角开始计算一直到右下角如下所示给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点

floyd算法的三重循环问题

三层循环的意思。第一层就是加入K的中间点，第二层和第三层循环是求每一对顶点在加入新的点后是否存在距离更近的路径，所以K只能放在最外层。也就是说你再加入新的点后，再进行判断每对顶点是否距离有变，就相当于一个前提条件。