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 1<<29 # define N 105 int mat[N][N],dis[N][N]; int minloop; void floyd(int n) { int i,j,k; for(k=1;k<=n;k++) { for(i=1;i<=n;i++) for(j=1;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=1;i<=n;i++) for(j=1;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=1;i<=n;i++) for(j=1;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=1;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 0; }
POJ 1734 Sightseeing trip(需输出最小环)
# include<cstdio> # include<cstring> # include<vector> # include<algorithm> using namespace std; # define pb push_back # define INF 1<<29 # define N 105 int mat[N][N],dis[N][N],mid[N][N],minloop; vector<int> vec; void dfs(int l,int r) { if(mid[l][r]==-1) 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=1;k<=n;k++) { for(i=1;i<k;i++) for(j=i+1;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=1;i<=n;i++) for(j=1;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=1;i<=n;i++) for(j=1;j<=n;j++) mat[i][j]=dis[i][j]=INF,mid[i][j]=-1; 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=1;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[0]); for(i=1;i<vec.size();i++) printf(" %d",vec[i]); printf("\n"); } return 0; }
相关证明理解请参考下面博客，讲解的非常好:
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 35 double dis[N][N]; void floyd(int n) { int i,j,k; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;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=1;i<=n;i++) for(j=1;j<=n;j++) dis[i][j]=(i==j)?1:0; } int main() { // freopen("in.txt","r",stdin); map<string,int> Hash; int i,n,m,num,flag,cas=1,u,v; char s1[N],s2[N]; double d; while(scanf("%d",&n)!=EOF&&n) { Hash.clear(); flag=num=0; init(n); for(i=1;i<=n;i++) { scanf("%s",s1); Hash[s1]=++num; } scanf("%d",&m); for(i=1;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=1;i<=n;i++) if(dis[i][i]>1.0) { flag=1; break; } if(flag) printf("Yes\n"); else printf("No\n"); } return 0; }
(3)传递闭包
POJ 3660 Cow Contest
# include<cstdio> # include<cstring> # include<algorithm> using namespace std; # define N 105 int f[N][N],beat[N],win[N]; void floyd(int n) { int i,j,k; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;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=0; memset(beat,0,sizeof(beat)); memset(win,0,sizeof(win)); memset(f,0,sizeof(f)); for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); f[u][v]=1; } floyd(n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) if(f[j][i]) //j beat i { win[j]++; beat[i]++; } } for(i=1;i<=n;i++) if(win[i]+beat[i]==n-1) ans++; printf("%d\n",ans); } return 0; }
(4)好题推荐(独立完成)
HDU 3631 Shortest Path //深入理解floyd
# include<cstdio> # include<cstring> # include<algorithm> using namespace std; # define INF 1<<29 # define N 305 int n,m,q; int dis[N][N]; int mark[N]; void floyd(int k) { int i,j; for(i=0;i<n;i++) for(j=0;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,0,sizeof(mark)); for(i=0;i<n;i++) for(j=0;j<n;j++) dis[i][j]=(i==j)?0:INF; } int main() { //freopen("in.txt","r",stdin); int i,j,u,v,w,op,cas=1; while(scanf("%d%d%d",&n,&m,&q)!=EOF&&(n+m+q)) { init(n); for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); dis[u][v]=min(dis[u][v],w); } if(cas>1) printf("\n"); printf("Case %d:\n",cas++); for(i=1;i<=q;i++) { scanf("%d",&op); if(op==0) { scanf("%d",&u); if(mark[u]) printf("ERROR! At point %d\n",u); else { mark[u]=1; 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 0; }
HDU 4034 Graph //深入理解floyd ,思维锻炼
# include<cstdio> # include<cstring> # include<algorithm> using namespace std; # define N 105 int dis[N][N]; int vis[N][N]; int floyd(int n) { int i,j,k,ans=n*(n-1); memset(vis,0,sizeof(vis)); for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(dis[i][k]+dis[k][j]<dis[i][j]) return -1; if(!vis[i][j]&&i!=k&&j!=k&&i!=j&&dis[i][k]+dis[k][j]==dis[i][j]) { ans--; vis[i][j]=1; } } return ans; } int main() { //freopen("in.txt","r",stdin); int cas,T,i,j,n,ans; scanf("%d",&T); for(cas=1;cas<=T;cas++) { scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&dis[i][j]); printf("Case %d: ",cas); ans=floyd(n); if(ans==-1) printf("impossible\n"); else printf("%d\n",ans); } return 0; }
4. 个人总结
Floyd算法有很多其他的应用，需要不断的积累，但是我相信只要能理解好floyd的DP思想(每个k点插入或者不插入相关路径),很多问题多能迎刃而解.
附录:关于Floyd判断环的可行性
注：该附录未经严格验证,请读者认真思考