2023年7月30日发(作者：)

floyd算法：我们真的明⽩floyd吗？图论⾥⼀个很重要的问题是最短路径问题.这个问题,在离散数学课上会考,数据结构与算法课上会考,图论课上会考,计算机⽹络⾥会考....解决最短路径问题有⼏个出名的算法:ra算法,最经典的单源最短路径算法n-ford算法,允许负权边的单源最短路径算法,其实是bellman-ford+队列优化,其实和bfs的关系更密⼀点算法,经典的多源最短路径算法今天我们讨论的是floyd算法,它⽤于解决多源最短路径问题,算法时间复杂度是O(n3).floyd算法为什么经典,因为它只有5⾏(或者4⾏)是的,没有特意的写成⼀⾏的代码.这个算法短的离谱,以致于我们通常直接将它背了下来当模板使⽤,⽽不像学dijkstra那时候⼀步步理解它是如何贪⼼的.那么,为什么floyd算法是这个样⼦的呢?或者说,为什么这样就能求出所有点到所有点的最短路径?谈起floyd算法,⼀般我们会说这是⼀个动态规划算法.(怪不得如此优美)为什么是个动态规划算法?因为它有递推公式:d[i][j]=min(d[i][j],d[i][k]+d[k][j])还有⼀点就是三重循环,k要写外⾯,⾥⾯的i,j是对称的,随便嵌套没所谓.这⼤概就是我们⼤部分⼈对floyd算法的了解.那么,我们其实没有解决核⼼问题,为什么这样就能解决问题,为什么是这个递推公式,是这个嵌套顺序?这⼀切都不像学长所说的那么显然...事实上,如果你明⽩了bellman-ford的正确性,你就会明⽩为什么floyd是可⾏的了.在这⾥我们不讨论floyd以外的算法,我们正⾯刚的最关键的地⽅是它的递推公式,它的递推公式写得抽象⼀点就是下图:简单来说,这个i到j的最短路径,我们可以找⼀个中间点k,然后变成⼦问题,i到k的最短路径和k到j的最短路径.也就是说,我们可以枚举中间点k,找到最⼩的d[i][k]+d[k][j],作为d[i][j]的最⼩值.这好像很合理啊,假如所有d[i][k]和d[k][j]都取了最⼩值的话,这个dp很dp.但是,d[i][k]和d[k][j]⼀开始都不⼀定取了最⼩值的啊!它们和d[i][j]⼀样,会不断变⼩.那么,会不会存在这种情况,d[i][j]取最⼩值时的k是某个x.⽽在最外循环k=x的时候,d[i][x]或者d[x][j]并没有取到最⼩值,但这个时候会执⾏d[i][j]=min(d[i][j],d[i][x]+d[x][j]),造成了d[i][j]并不能取到真正的最⼩值.答案当然是,并不会出现这种情况.我们今天的重点就是来讨论为什么不会出现这种情况.我们需要证明⼀个很致命的结论:假设i和j之间的最短路径上的结点集⾥(不包含i,j),编号最⼤的⼀个是x.那么在外循环k=x时,d[i][j]肯定得到了最⼩值.怎么证明,可以⽤强归纳法.设i到x中间编号最⼤的是x1,x到j中间编号最⼤的是x2.由于x是i到j中间编号最⼤的,那么显然x1