[图论]Floyd 算法小结

浏览数：31 / 时间：2015年06月09日

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;
}
HDU 1599

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;
}
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 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;
}
POJ 2240

(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;
}
POJ 3660

(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 3631

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;
}
HDU 4034

   

4. 个人总结

Floyd算法有很多其他的应用，需要不断的积累，但是我相信只要能理解好floyd的DP思想(每个k点插入或者不插入相关路径),很多问题多能迎刃而解.

 

附录:关于Floyd判断环的可行性

 

注：该附录未经严格验证,请读者认真思考 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 算法 图论 图 小结 floyd 算法 图论 图 小结 floyd

相关文章

随机文章

您可能还喜欢

您可能还喜欢