Floyd算法为什么把k放在最外层?

Floyd算法为什么把k放在最外层?

采用动态规划思想,表示和之间可以通过编号为的节点的最短路径。

初值为原图的邻接矩阵。

则可以从转移来,表示到不经过这个节点。

也可以从转移过来,表示经过这个点。

意思即

然后你就会发现最外层一维空间可以省略,因为只与有关。

虽然这个算法非常简单,但也需要找点时间理解这个算法,就不会再有这种问题啦。