最短路（Floyd）

关于最短的先记下了

Floyd算法：

  比较精简准确的关于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++)
    {
        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];
            }
        }
    }

最短路（Floyd）

原文：http://www.cnblogs.com/yinqx/p/4977501.html