最短路（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

巴特西

最短路（Floyd）

最新文章

热门文章