2021年hznu寒假集训第九天

最短路相关概念

Floyd

我们定义一个数组 dis[k][x][y] ，表示只允许经过结点 V1 到 Vk ，结点 x 到结点 y 的最短路长度。

很显然， dis[n][x][y] 就是最终结点 x 到结点 y 的最短路长度。

dis[0][x][y] 是 x 与 y 的边权，或者 0 ，或者 inf （当 x 与 y 间有直接相连的边的时候，为它们的边权；当 x = y 的时候为零，因为到本身的距离为零；当 x 与 y 没有直接相连的边的时候，为 inf ）

dis[k][x][y] = min(dis[k-1][x][y], dis[k-1][x][k]+dis[k-1][k][y]) （ dis[k-1][x][y] 为不经过 k 点的最短路径，而 dis[k-1][x][k]+dis[k-1][k][y] 为经过了 k 点的最短路）。

上面两行都显然是对的，所以说这个做法空间是 O(