又众所周知，floyd要三层循环，遍历的顺序是kij（此处kij和上文代表意思相同），也就是先枚举一个点，然后再枚举所有点能否经过这个点更新路径；
那如果把遍历的顺序改成ijk呢
我写了一个程序，遍历顺序取ijk，交上去WA，这证明了ijk的遍历顺序是错的；
为什么不能是ijk？
我画了一张图（图2）
由瞪眼法得，1点到5点的最短路长度为6（即1->3->4->5)
我们假设此时i = 1，j = 5，k = 4
由于1和4之间目前没有最短路（在数组里设成一个非常大的数，以下称为无穷大），可以发现无穷大+2不会小于无穷大，所以不会更新
这样一直不更新，i不再等于1，j不再等于5，造成了WA
如果是kij就不一样了，即使一次没更新，之后也能求出最短路
现在，k依然和上文一样等于4，但是遍历一遍ij，可以发现5和3之间的最短路等于4，不是无穷大
等k到3时，i再次等于1，j再次等于5，求出最短路
你可以理解成动态规划，遍历是要有顺序的，把i到j的最短路看作一个状态，要用到的状态并不全，有的还并未求出，就导致了状态转移方程里包含无穷大
目前没有人把floyd看成动态规划，如有错误，请提出，我会尽快修改
到此，ijk为什么不对以及kij为什么对已经说明了
最后补充一点，图2中的数据用ijk的floyd可以过，因为ijk不可能按这个顺序遍历，不能直接就i = 1，j = 5，k = 4，只是为了简单易懂出了这组数据
但是，如果数据范围特别大呢？ijk遍历就会WA
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/87197.html