最短路（Floyd）

 

关于最短的先记下了

Floyd算法：

  1.比较精简准确的关于Floyd思想的表达：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设maze(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查maze(AX) + maze(XB) < maze(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置maze(AB) = maze(AX) + maze(XB)，这样一来，当我们遍历完所有节点X，maze(AB)中记录的便是A到B的最短路径的距离。

代码：    for(int k= 1;k <= n;k++)//固定了k，把所有的i到j都处理完才会移动到下一个k    {        for(int i= 1;i <= n;i++)        {            for(int j = 1;j<= n;j++)            {                if(maze[i][j] > maze[i][k] + maze[k][j])                    maze[i][j] = maze[i][k] + maze[k][j];            }        }    }

2.用Floyd还可以判环

代码：

 int mi=INF;                                                

for(int k=1;k<=n;k++)    {                                                                                                                for(int i=1;i<k;i++)         {             for(int j=1;j<j;j++)             {                  mi=min(ma[i][j]+dis[j][k]+dis[k][i],mi);//已经有最短路1的情况下再找一次最短路2             }         }         for(int i=1;i<=n;i++)         {             for(int j=1;j<=n;j++)             {                 if(ma[i][k]>ma[i][k]+ma[j][k])                     ma[i][j]=ma[i][k]+ma[k][j];//找最短路，是从第一个点开始             }         }     }1->2值为1，2->3值为2,3->4值为3,4->1值为4，则第一次存在从1到3的最短路，再寻找时找到了1到4,4到3的路径，则形成了环，而且是最小的。

  讲的很详细的一个博客：http://m.blog.csdn.net/blog/qq909157370/9225109

 

转载于:https://www.cnblogs.com/yinqx/p/4977501.html