floyd用于求出当n较小的时候,图中任意两点的最小距离
时间复杂度O(n^3)
有个问题就是,为什么枚举中间点的循环是放在最外面?
我们的循环是这样的:
for(int k=0;k<=9;k++){
for(int i=0;i<=9;i++){
for(int j=0;j<=9;j++){
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
如果k放在外层,k是从小到大逐渐增长的。
可以发现:dist[i][k]一定在dist[i][j]之前被更新过,dist[k][j]一定在dist[i][j]之前被更新过
比如说,k=3 , 而在k=0的时候,所有的dp[i][j]都被更新过一次了。
我们使用的都是目前最优秀的状态。
但如果把k放在里面:
for(int i=0;i<=9;i++){
for(int j=0;j<=9;j++){
for(int k=0;k<=9;k++){
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
显然,当i,j都很小的时候,k已经可以跑到9了。
所以 dp[i][k] 并不会在 dp[i][j]被更新前更新。