-
多源最短路算法(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]); `
标签:图论,松弛,浅谈,短路,枚举,考虑
From: https://www.cnblogs.com/Kazdale/p/17518758.html