弗洛伊德算法怎么理解（Floyd算法的优缺点分析）

：暂无数据 2026-07-20 01:00:02 ：0

今天给各位分享Floyd算法的优缺点分析的知识，其中也会对Floyd算法的优缺点分析进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录

Floyd算法的优缺点分析
跪求弗洛伊德算法一个错误的解释：
弗洛伊德与地杰斯特拉算法的区别
弗洛伊德算法和地杰斯特拉算法的区别

Floyd算法的优缺点分析

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

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 );
for( int i= 1; i《 top; ++i ) printf(“ %d“, path );
puts(““);
}else puts(“No solution.“);

return 0;
}

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

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