虽然我还在学动态规划, 但这并不影响我去试图研究 floyed, 在对 floyed 算法进行研究了 40min 后, 我感觉我似乎应该好像是勉强理解了 floyed 算法
- for(int k=1;k<=n;k++)
- for(int i=1;i<=n;i++)
- for(int j=1;j<=k;j++)
- if(f[i][k]+f[k][j]<f[i][j])
- f[i][j]=f[i][k]+f[k][j];
以上为 floyed 的基础模板 Floyed 算法, 用来计算这个图上任意点对间的距离, 3 重循环, 简单思考便知道, k 表示要 i - k 和 k - j 去尝试更新 i j
Floyed 算法最神奇的地方在于 k 循环的位置, 为什么要放在最外层而不是最内层, 简单思索后, 放在最外层是用 k 点一次更新所有点的距离, 而放在最内层则是将 ij 的距离尝试用所有点 k 去更新, 乍一看似乎没有什么区别? 好像是一样的, 但是我们实际手动推算就会发现, 没有这么简单!(没错就是手推, 虽然暴力, 但是极其有效)
我们来想想这有什么区别先:
外层: 用 k 更新所有 ij
内层: 枚举所有 k 来更新 ij
区别就在于这两种更新方式的顺序变了, 那么放在内层会产生如何影响呢?
- for(int i=1;i<=n;i++)
- for(int j=1;j<=k;j++)
- for(int k=1;k<=n;k++)
- if(f[i][k]+f[k][j]<f[i][j])
- f[i][j]=f[i][k]+f[k][j];
如果 k 层在最内层, 就是每次更新 ij 时都要枚举一遍 k 点, 但实际上, ik 却没有更新过, 所以导致 ij 无法更新, 然后就会产生恶性循环, 然后 boom 的炸掉, 到最后也许只有几个幸运点对成功更新出正确距离
但是在外层呢? 我们不得不赞叹 floyed 算法的强大与神奇, 因为 k 点一次更新了所有的点对, 所以在进行后续更新操作时, ik 的距离是肯定被更新过了的, 保证了算法的正确性, 感觉之所以说 floyed 用到了动态规划思想的原因实际是下一个 ij 中, 距离是否被更新, 只与与 j 直接相连的 k 点的所记录的值, 即 ik 和 kj 这个定值有关
最后感叹 floyed 算法的强大与神奇
来源: http://www.bubuko.com/infodetail-2524577.html