全源最短路问题–Floyd算法

Floyd算法，也就是弗洛伊德算法，用来解决全源最短路问题。就是对给定的图G，求任意两点u，v之间的最短路径长度，时间复杂度为O(n^3)。

由于n^3的复杂度决定了顶点数n的限制约在200以内，因此使用邻接矩阵来实现Floyd算法是非常合适且方便的。

Floyd算法基于一个事实：
如果存在顶点k，使得以k作为中介点时，顶点i和顶点j的当前最短距离缩短，则使用顶点k作为顶点i和顶点j的中介点，即
dis[i][k] +dis[k][j] < dis[i][j] 时，令

dis[i][j] = dis[i][k] +dis[k][j]
其中dis[i][j]表示从顶点i到顶点j的最短距离。

//基于上面的事实，Floyd算法的模板流程如下：

枚举顶点 k 属于 [1,n]
    以顶点 k 作为中介点，枚举所有顶点对 i 和 j （i 属于 [1,n], j 属于 [1,n]） 
        如果 dis[i][k] + dis[k][j] < dis[i][j] 成立
            赋值 dis[i][j] =  dis[i][k]+dis[k][j] 





//Floyd算法程序具体实现

#include <cstdio>
#include <algorithm>

using namespace std;



const int INF=0x3fffffff;

const int MAXV=200;

//n为顶点数，m为边数 
int n,m;

//dis[i][j] 表示顶点i和顶点j之间的最短距离 
int dis[MAXV][MAXV];


void Floyd()
{

    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {

            for(int j=0;j<n;j++)
            {
                if( dis[i][k] != INF && dis[k][j]!=INF 
                    && dis[i][k]+dis[k][j]<dis[i][j]  )
                {

                    //找到更短的路径
                    dis[i][j] = dis[i][k] + dis[k][j];


                }

            }

        }


    }




}



int main()
{

    int u,v,w;

    //dis数组赋初值 
    fill( dis[0],dis[0]+MAXV*MAXV,INF  );

    //顶点数n，边数m 
    scanf("%d%d",&n,&m);

    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);

        //以有向图为例进行输入 
        dis[u][v]=w;



    }


    Floyd();

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {

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

        }

        printf("\n");

    }




}

注意点

对于Floyd算法来说，不能将程序中的最外层的k循环放到内层。
也就是不能产生i->j->k的三重循环，这会导致出错。

出错原因

如果当较后访问的dis[u][v]有了优化之后，
前面访问的dis[i][j]会因为已经被访问而无法获得进一步的优化。