浅谈图论-JZTXT

多源最短路算法（Floyd）
说到最短路，就不得不提到松弛。
所谓松弛，就是当存在\(w_{u,v}>w_{u,k}+w_{k,v}\)时，令\(w_{u,v}=w_{u,k}+w_{k,v}\)
一般来说，松弛操作后，我们会用松弛后的边不断松弛其他边，而这，就是大部分最短路算法的思路。
思考一下，若用DP的思想考虑，那么我们易设出状态\(f_{i,j}\)表示从\(i\)到\(j\)的最短路，但是这个状态显然具有后效性，因为我们显然无法一遍就能转移出\(f_{i,j}\)的正确结果，需要不断对其他边进行松弛操作才能得出最后答案，所以同为\(f_{i,j}\)的值在不同阶段会有不同的值。
那么考虑加一维表示松弛阶段，则最显然表示松弛阶段的方式是边，然而边太多且一个边能松弛其他边的数量及其有限，故考虑点。
则设\(f_{k,i,j}\)为只考虑前\(k\)个点时，从\(i\)到\(j\)的最短路。
那么可以推出转移式\(f_{k,u,v} = min(f_{k,u,v},f_{k-1,u,k}+f_{k-1,k,v})\)
不断枚举\(k\)，然后枚举所有\(i,j\)，用\(k\)这个端点去更新它们。
观察到\(f_{k,i,j}\)的值只与\(f_{k-1,i,j}\)有关，故可以用滚动数组压成二维。
代码如下:

for (int k = 1; k <= n; ++k) 
        for (int u = 1; u <= n; ++u)
            for (int v = 1; v <= n; ++v)  f[u][v] = min(f[u][v], f[u][k] + f[k][v]); `

JZTXT

浅谈图论

多源最短路算法（Floyd）