图论学习笔记·$Floyd$ $Warshall$

对于图论——虽然本蒟蒻也才入门……于是有了这篇学习笔记(qwq)

一般我们对于最短路的处理，本蒟蒻之前都是通过构建二维数组的方式然后对每两个点进行1次深度或者广度优先搜索，即一共进行(n)^2遍深度（DFS）或广度优先搜索（BFS）……直到学习了Floyd算法(qwq)

先上核心代码(Code)：

for(k=1;k<=n;k++)
{ 
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            {
                if(e[i][j]>e[i][1]+e[1][j]) e[i][j]=e[i][1]+e[1][j];
            }
    }
}

这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1号和2号顶点进行中转……允许经过1~(n)号所有顶点进行中转，求任意两点之间的最短路程。

用一句话概括就是：从(i)号顶点到(j)号顶点只经过前(k)号点的最短路程。

其实，这只是一种名叫“动态规划”（(dp)）的思想怎么可能告诉你我也不会(QAQ)