弗洛伊德算法是干什么的

1. 弗洛伊德的算法（Floyd’s algorithm ）

假设这个图的weight matrix存在map[5][5]中，

for(intk=0;k<5;k++)
for(inti=0;i<5;i++)
for(intj=0;j<5;j++)if(i!=j){
if(map[i][k]+map[k][j]<map[i][j])
map[i][j]=map[i][k]+map[k][j];
}

处理完之后map[i][j]存的就是i，j之间的最短路径长度。

简单的说，当执行完一次最外层循环时，map记录的时i，j之间允许使用中间节点｛0, ..., k｝的最短路径。

2. 【数据结构】最短路径之迪杰斯特拉(Dijkstra)算法与弗洛伊德(Floyd)算法

迪杰斯特拉(Dijkstra)算法核心： 按照路径长度递增的次序产生最短路径。

迪杰斯特拉(Dijkstra)算法步骤：（求图中v0到v8的最短路径）并非一下子求出v0到v8的最短路径，而是 一步一步求出它们之间顶点的最短路径 ，过过程中都是 基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得出源点与终点的最短路径 。

弗洛伊德(Floyd)算法是一个经典的 动态规划算法 。

3. 弗洛伊德与地杰斯特拉算法的区别

最大的区别是算法的时间复杂度
弗洛伊德算法的复杂度最低也是N的三次方 如果是竞赛的话你用弗洛伊德很不幸 你会超时
但是地杰斯特拉算法的复杂度就很低了可以达到期望logn级别 比N的三次方的算法就快了很多
还有一个区别就是在做最短路问题的时候迪杰斯特拉算法不适用于边有负权值的图
当碰到边有负权时 你可以选择SPFA算法 这是迪杰斯特拉算法的优化版 对稀疏图有不错的效果
顺带一提 SPFA是中国人优化的

4. 弗洛伊德算法求出最短距离

（1）利用二维数组dist[i][j]记录当前vi到vj的最短路径长度，数组dist的初值等于图的带权邻接矩阵;

（3）依次向S中加入v0,v1…vn-1，每加入一个顶点，对dist[i][j]进行一次修正：设S={v0,v1…vk-1}，加入vk，则dist(k)[i][j]=min{dist(k-1)[i][j]，dist(k-1)[i][k]+dist(k-1)[k][j]}。

dist(k)[i][j]的含义：允许中间顶点的序号最大为k时从vi到vj的最短路径长度。
dist(n-1)[i][j]就是vi到vj的最短路径长度。

弗洛伊德最短距离算法（FloydShortestPathAlgorithm）又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
中文名弗洛伊德最短距离算法
外文名FloydShortestPathAlgorithm
所属学科IT
所属领域程序设计
简介
最短路问题是网络最优化中一个基本而又非常重要的问题，这一问题相对比较简单，在实际生产和生活中经常遇到，许多的网络最优化问题可以化为最短路问题，或者用最短路算法作为其子程序.因此，最短路的用途已远远超出其表面意义迄今为止，所有最短路算法都只对不含负回路的网络有效，实际上对含有负回路的网络，其最短路问题是NP困难的，因此本研究所讨论的网络也不含负回路.此外，如果将无向图每条边用两条端点相同、方向相反的弧来代替，可以将其化为有向图，因而不讨论无向图.本研究中未述及的术语、记号。
Floyd算法是一种用于寻找给定加权图中顶点间最短路径的算法，以1978年图灵奖获得者斯坦福大学计算机科学系教授RobertW．Floyd命名。Floyd算法采用动态规划的原理计算两两顶点间最短路径，主要解决网络路由寻找最优路径的问题。

5. Floyd算法的优缺点分析

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

6. 求弗洛伊德算法的详细解释~

floyd算法思想：1，构建一个邻接矩阵存储任意两点之间的权值如图D0.

2、例如求v1,v4之间的最短路径。先增加v2做中间顶点，D[1][4]=∞。if（D[1][4]>D[1][2]+D[2]4]）=6+4）D[1][4]=10;这样就可以了。

3、如不能在离得较远的两点(例v1,v9）直接得到上述可以满足if的中间点，则跟据你书本的代码可以先构建原点到中间点的最短路径，继而就可以求得vi,v9之间的最短路径

7. 跪求 弗洛伊德算法 一个错误的解释：

floyd算法用以解决所有点对最短路径。

floyd算法基本思想是递推，动态规划。我们记 dp[j][k] 表示图中顶点 i 到 j 的最短路径，且该最短路径中，所经过的中间顶点(不包括 i, j) 的范围为 [1,k]，由此我们可以得到以下递推式：

dp[j][k]= w[j] 如果 k== 0

dp[j][k]= min{ dp[k][k-1]+ dp[k][j][k-1] } 如果 k>= 1。

实际中，空间上我们可以减少一维。

floyd算法同样可以来解决一些其它问题

1) 有向图的最小(或最大)环

这个问题答案其实就是自身到自身的最短路径，运行完 floyd 后，对每个顶点取自身到自身距离的最小者。

2) 无向图的最小环

根据以上的递推式，dp[j][k] 表示 i 到 j 的最短路径，且该最短路径中，所经过的中间顶点(不包括 i, j) 的范围为 [1,k]。

此时我们可以枚举出顶点序列最大为 k+ 1 的所有最小环，如何枚举：设与顶点序列最大的顶点 k+ 1 相连的两个顶点为 x, y，x,y 须满足 x, y<= k。这样最小环构成为 边<x,k+1> 边<k+ 1, y> 及 x 到 y 的最短路径。

Poj 1734 Sightseeing trip

#include <stdio.h>
#include <stdlib.h>

int const N= 110, inf= 5000000;
int mat[N][N], dist[N][N], pre[N][N], path[N], n, m, top= 0, p;

#define min(a,b) ((a)<(b)?(a):(b))

int main(){
scanf("%d%d",&n,&m );
for( int i= 0; i<= n; ++i )
for( int j= 0; j<= n; ++j ){
mat[j]= inf; dist[j]= inf; pre[j]= j; }
while( m-- ){
int u, v, d;
scanf("%d%d%d",&u,&v,&d);
mat[v]= min( mat[v], d );
mat[v]= mat[v];
dist[v]= mat[v]; dist[v]= mat[v];
}
int ans= inf;
for( int k= 1; k<= n; ++k ){
for( int x= 1; x< k; ++x )
for( int y= 1; y< x; ++y ){
if( mat[x][k]+ mat[k][y]+ dist[x][y]< ans ){
ans= mat[x][k]+ mat[k][y]+ dist[x][y];
top= 0; path[top++]= k; p= x;
while( p!= y ){
path[top++]= p; p= pre[p][y];
}
path[top++]= y;
}
}
for( int i= 1; i<= n; ++i )
for( int j= 1; j<= n; ++j )
if( dist[k]+ dist[k][j]< dist[j] ){
dist[j]= dist[k]+ dist[k][j];
pre[j]= pre[k]; }
}
if( top> 0 ){
printf("%d", path[0] );
for( int i= 1; i< top; ++i ) printf(" %d", path );
puts("");
}else puts("No solution.");

return 0;
}

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

1.定义概览
Floyd-Warshall算法（Floyd-Warshall
algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。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-Warshall
algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。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两点之间最短路径所必须经过的点

9. 弗洛伊德算法的姓氏

c语言文件读写操作裤缺薯代码
算法之“弗洛伊德（Floyd）算法”

weixin_34239169
转载
关注
0点赞·271人阅读
弗洛伊德算法
弗洛伊德（Floyd）算法是 Robert W. Floyd（罗伯特·弗洛伊德）于胡者 1962 年发表在“Communications of the ACM”上，Robert W．Floyd 在 1978 年获得了图灵奖。用于从给定的加权图中查找所有顶点间的最短路径问题。作为该算扮卜法的结果，它将生成矩阵，该矩阵将表示从任何顶点到图中所有其他顶点的最小距离。
弗洛伊德算法步骤
1.根据输入图的二维数组初始化输出 dist 二维数组。
2.利用中间顶点，逐个挑选所有顶点并更新所有最短路径。
3.选择顶点 k 作为中间顶点时，我们将顶点 {0,1,2，... k-1} 视为中间顶点，i、j 表示源顶点和目标顶点。
4.如果 k 不是从 i 到 j 的最短路径中的中间顶点，我们保持 dist [i] [j]的值不变。
5.如果 k 是从 i 到 j 的最短路径中的中间顶点，并且 dist[i][k] + dist[k][j] < dist[i][j]，则更新 dist[i][j] = dist[i][k] + dist[k][j]。