[图论]Floyd 算法小结

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Floyd 算法小结

By Wine93 2013.11

1. Floyd算法简介

Floyd算法利用动态规划思想可以求出任意2点间的最短路径,时间复杂度为O(n^3),对于稠密图, 效率要高于执行|V|次Dijkstra算法.

核心代码如下:

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

相关应用 : 有向图:①求任意2点间最短路径 ②求最小环(可判断负圈,检查dis[i][i]) ③求传递闭包

无向图:(无负权边): ①求任意2点间最短路径 ②求最小环

注意:对于有负权边的无向图，会出现很多意想不到的错误，请谨慎使用floyd。

2. 个人心得

对于floyd，我认为最重要的是理解k循环这层，每枚举一个k，代表下面代表的点对(i，j)之间的最短路有可能会通过k这点而变小,也就是说在i到j的这条简单路径上插上k这个点，有可能会使路径长度变小。还有就是floyd求出来的最短路径肯定是简单路径(无向图)

关于可Floyd解的题其顶点数都比较小，根据这点会给我们一点暗示.

如果要输出floyd所求相关路径，我们可以记录mid[i][j](表示i到j这条路径中插入的点k),这样通过不断递归，就可以求出整条路径

3. Floyd算法的应用举例

(1) 求无向图最小环

HDU 1599 find the mincost route

# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;# define INF <<
# define N int mat[N][N],dis[N][N];
int minloop;void floyd(int n)
{
int i,j,k;
for(k=;k<=n;k++)
{
for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(i!=j&&i!=k&&j!=k&&dis[i][j]+mat[j][k]+mat[k][i]<minloop)
minloop=dis[i][j]+mat[j][k]+mat[k][i];
for(i=;i<=n;i++)
for(j=;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}void init(int n)
{
int i,j;
minloop=INF;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
mat[i][j]=mat[j][i]=dis[i][j]=dis[j][i]=INF;
}int main()
{
// freopen("in.txt","r",stdin);
int i,n,m,u,v,w;
while(scanf("%d%d",&n,&m)!=EOF)
{
init(n);
for(i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
if(w<mat[u][v])
mat[u][v]=mat[v][u]=dis[u][v]=dis[v][u]=w;
}
floyd(n);
if(minloop==INF) printf("It's impossible.\n");
else printf("%d\n",minloop);
}
return ;
}

HDU 1599

POJ 1734 Sightseeing trip(需输出最小环)

# include<cstdio>
# include<cstring>
# include<vector>
# include<algorithm>
using namespace std;# define pb push_back
# define INF <<
# define N int mat[N][N],dis[N][N],mid[N][N],minloop;
vector<int> vec;void dfs(int l,int r)
{
if(mid[l][r]==-) return;
dfs(l,mid[l][r]);
vec.pb(mid[l][r]);
dfs(mid[l][r],r);
}void floyd(int n)
{
int i,j,k;
for(k=;k<=n;k++)
{
for(i=;i<k;i++)
for(j=i+;j<k;j++)
{
if(dis[i][j]+mat[j][k]+mat[k][i]<minloop)
{
minloop=dis[i][j]+mat[j][k]+mat[k][i];
vec.clear();
vec.pb(i);
dfs(i,j);
vec.pb(j);
vec.pb(k);
}
}
for(i=;i<=n;i++)
for(j=;j<=n;j++)
{
if(dis[i][k]+dis[k][j]<dis[i][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
mid[i][j]=k;
}
}
}
}void init(int n)
{
int i,j;
minloop=INF;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
mat[i][j]=dis[i][j]=INF,mid[i][j]=-;
vec.clear();
}int main()
{
//freopen("in.txt","r",stdin);
int i,j,n,m,u,v,w;
while(scanf("%d%d",&n,&m)!=EOF)
{
init(n);
for(i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
if(w<mat[u][v])
dis[u][v]=dis[v][u]=mat[u][v]=mat[v][u]=w;
}
floyd(n);
if(minloop==INF)
{
printf("No solution.\n");
continue;
}
printf("%d",vec[]);
for(i=;i<vec.size();i++)
printf(" %d",vec[i]);
printf("\n");
}
return ;
}

POJ 1734

相关证明理解请参考下面博客，讲解的非常好:

http://www.kaixinwenda.com/article-aclion-8074848.html

(2)判断有向图是否有正环

POJ 2240 Arbitrage

# include<cstdio>
# include<cstring>
# include<string>
# include<map>
# include<algorithm>
using namespace std;# define N
double dis[N][N];void floyd(int n)
{
int i,j,k;
for(k=;k<=n;k++)
for(i=;i<=n;i++)
for(j=;j<=n;j++)
dis[i][j]=max(dis[i][j],dis[i][k]*dis[k][j]);
}void init(int n)
{
int i,j;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
dis[i][j]=(i==j)?:;
}int main()
{
// freopen("in.txt","r",stdin);
map<string,int> Hash;
int i,n,m,num,flag,cas=,u,v;
char s1[N],s2[N];
double d;
while(scanf("%d",&n)!=EOF&&n)
{
Hash.clear();
flag=num=;
init(n);
for(i=;i<=n;i++)
{
scanf("%s",s1);
Hash[s1]=++num;
}
scanf("%d",&m);
for(i=;i<=m;i++)
{
scanf("%s %lf %s",s1,&d,s2);
u=Hash[s1];
v=Hash[s2];
dis[u][v]=max(dis[u][v],d);
}
floyd(n);
printf("Case %d: ",cas++);
for(i=;i<=n;i++)
if(dis[i][i]>1.0)
{
flag=;
break;
}
if(flag) printf("Yes\n");
else printf("No\n");
}
return ;
}

POJ 2240

(3)传递闭包

POJ 3660 Cow Contest

# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;# define N
int f[N][N],beat[N],win[N];void floyd(int n)
{
int i,j,k;
for(k=;k<=n;k++)
for(i=;i<=n;i++)
for(j=;j<=n;j++)
f[i][j]|=(f[i][k]&&f[k][j]);
}int main()
{
int i,j,n,m,u,v,ans;
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=;
memset(beat,,sizeof(beat));
memset(win,,sizeof(win));
memset(f,,sizeof(f));
for(i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
f[u][v]=;
}
floyd(n);
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
if(f[j][i]) //j beat i
{
win[j]++;
beat[i]++;
}
}
for(i=;i<=n;i++)
if(win[i]+beat[i]==n-)
ans++;
printf("%d\n",ans);
}
return ;
}

POJ 3660

(4)好题推荐(独立完成)

HDU 3631 Shortest Path //深入理解floyd

# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;# define INF <<
# define N int n,m,q;
int dis[N][N];
int mark[N];void floyd(int k)
{
int i,j;
for(i=;i<n;i++)
for(j=;j<n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}void init(int n)
{
int i,j;
memset(mark,,sizeof(mark));
for(i=;i<n;i++)
for(j=;j<n;j++)
dis[i][j]=(i==j)?:INF;
}int main()
{
//freopen("in.txt","r",stdin);
int i,j,u,v,w,op,cas=;
while(scanf("%d%d%d",&n,&m,&q)!=EOF&&(n+m+q))
{
init(n);
for(i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
dis[u][v]=min(dis[u][v],w);
}
if(cas>) printf("\n");
printf("Case %d:\n",cas++);
for(i=;i<=q;i++)
{
scanf("%d",&op);
if(op==)
{
scanf("%d",&u);
if(mark[u])
printf("ERROR! At point %d\n",u);
else
{
mark[u]=;
floyd(u);
}
}
else
{
scanf("%d%d",&u,&v);
if(!mark[u]||!mark[v])
printf("ERROR! At path %d to %d\n",u,v);
else if(dis[u][v]==INF)
printf("No such path\n");
else
printf("%d\n",dis[u][v]);
}
}
}
return ;
}

HDU 3631

HDU 4034 Graph //深入理解floyd ,思维锻炼

# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;# define N
int dis[N][N];
int vis[N][N];int floyd(int n)
{
int i,j,k,ans=n*(n-);
memset(vis,,sizeof(vis));
for(k=;k<=n;k++)
for(i=;i<=n;i++)
for(j=;j<=n;j++)
{
if(dis[i][k]+dis[k][j]<dis[i][j])
return -;
if(!vis[i][j]&&i!=k&&j!=k&&i!=j&&dis[i][k]+dis[k][j]==dis[i][j])
{
ans--;
vis[i][j]=;
}
}
return ans;
}int main()
{
//freopen("in.txt","r",stdin);
int cas,T,i,j,n,ans;
scanf("%d",&T);
for(cas=;cas<=T;cas++)
{
scanf("%d",&n);
for(i=;i<=n;i++)
for(j=;j<=n;j++)
scanf("%d",&dis[i][j]);
printf("Case %d: ",cas);
ans=floyd(n);
if(ans==-)
printf("impossible\n");
else
printf("%d\n",ans);
}
return ;
}