关于 floyd 中为什么 k 放在最外层的个人看法

Zxsoul · 2024-02-25 20:50:25 · 个人记录

关于 floyd 中为什么 k 放在最外层的个人看法

简单的讲，按照最短路比如 dij 的代码运行思路来讲，最短路的来源都是从先是点与点直接相连来更新最短路，然后再是三个点，更多点，也就是说，最短路是从两点之间的路径，一直延伸到整张图才形成。

这就与DP状态类似，你只有把 f[1][k] 内所有的状态都求出来之后才能去求 f[2]

那么我们来看 k 放在外层和放在内层的区别

• 当 k 放在外层的时候，他会与每一个 i, j 都进行一遍，此时可以发现，与 k 相连的相邻节点都已经被更新过了，这相当于上边的 f[1] 状态完成
• 但是当 k 放在内层的时候，k 只能更新 i ,j 这一组，

换个角度来讲，我们可以把 k 中节点作为状态的层级来分，也就是说，无论选择中节点的顺序是如何的，最终答案是一样的，所以这个中节点的顺序没有关系，而它的作用只不过是随机挑选一个节点，让她率先更新相连的路径，之后在枚举其他节点，以此扩大状态，节点的选取无所谓，但是过程是一样的，都是几个节点的路径，扩展到更长节点的路径，所以这里大可把k 认为是DP中状态的层级划分。

总的来说，中节点的选取对答案不会造成影响，说明无论选择哪个中节点，DP的过程都是一样的，而DP的过程都是从小节点路径，扩展到大节点路径，所以，这里的 k 相当于一个状态层级划分的存在，即 f[1] f[2] f[3] k=1,2,3,4,5...