Floyed

1.定义

　　可解任意两点间的最短路径

可判有向图或负权的最短路径问题，也可用于计算有向图的传递闭包

2.算法描述

　　　　简单点说，就是暴力遍历

　　　　时间复杂度O（n^3）

下面是简简单单的代码：

#include <cstdio>

int main()

{

    int e[][],k,i,j,n,m,t1,t2,t3;

    int inf=; //用inf(infinity的缩写)存储一个我们认为的正无穷值

    //读入n和m，n表示顶点个数，m表示边的条数

    scanf("%d %d",&n,&m);

    //初始化

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

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

            if(i==j) e[i][j]=;

              else e[i][j]=inf;

    //读入边

    for(i=;i<=m;i++)

    {

        scanf("%d %d %d",&t1,&t2,&t3);

        e[t1][t2]=t3;

    }

    //Floyd-Warshall算法核心语句

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

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

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

                if(e[i][j]>e[i][k]+e[k][j] )

                    e[i][j]=e[i][k]+e[k][j];

    //输出最终的结果

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

    {

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

        {

            printf("%10d",e[i][j]);

        }

        printf("\n");

    }

    return ;

}

下面是可以判断负环的代码：

#include<iostream>

#include<cstring>

using namespace std;

#define inf 0x3f3f3f3f

#define maxn 555

int mmp[maxn][maxn];

int x,y,z,t,n,w,m;

bool floyd()

{

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

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

        {

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

            {

                if(mmp[i][k]+mmp[k][j]<mmp[i][j])

                    mmp[i][j]=mmp[i][k]+mmp[k][j];

            }

            if(mmp[i][i]<)

                return ;

        }

    return ;

}

int main()

{

    cin>>t;

    while(t--)

    {

        memset(mmp,inf,sizeof(mmp));

        cin>>n>>m>>w;

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

            mmp[i][i]=;

        while(m--)

        {

            cin>>x>>y>>z;

            if(z<mmp[x][y])

            {

                mmp[x][y]=z;

                mmp[y][x]=z;

            }

        }

        while(w--)

        {

            cin>>x>>y>>z;

            mmp[x][y]=-z;

        }

        if(floyd())

            cout<<"YES"<<endl;

        else

            cout<<"NO"<<endl;

    }

    return ;

}