floyd算法

floyd算法基于动态规划算法,$dist[i][j][k]$表示当只途经$1$到$k$的点时(起始点和终止点不算),i到j的最短路长度。特别的$dist[i][j][0]$表示初始时$i$到$j$的边长。

状态计算:显然从$i$到$j$且只经过$1$到$k$的路径分为两类

• 从$i$到$j$且只经过$1$到$k-1$的路径
• 从$i$到$k$再从$k$到$j$且只经过$1$到$k-1$的路径

$dist[i][j][k]=min(dist[i][j][k-1],dist[i][k][k-1]+dist[k][j][k-1])$

由于在第三维为$k$的时候，需要用到$k-1$维，所以需要先枚举$k$。

显然 $dist[i][k][k-1]和dist[i][k][k]$相同，所以$k$那维是多余的

$dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])$