按照经典路径很多人学习最短路算法时学习的可能都是Floyd算法它有一个好处——如果学习了动态规划那么可以“借力”但实际上如何不予置评它还有一个好处——代码嘎嘎容易学会。个人观点学Floyd算法应该学完单源非负权的Dijkstra算法和单源可负权的Bellman-Frod算法之后再学。原因在于这两个算法的核心操作是“松弛”我们先从松弛的角度来给一个感性认识然后从DP的角度将分阶段计算、Floyd算法、三维优化为二维等操作似乎更好。1、啥是松弛做小灰机从北京→上海直达比北京→郑州→上海贵那么郑州就是一个中转站途经它使得钱包压力更小了。我们把所有城市都当中转站每次都更新机票价格——这就是算法干的事情。跑偏了啥是松弛呢如果从i到k再从k到j比直接走i到j更近那么途径k使得原本连接i,j的橡皮筋就松了路径变短。2、代码伪层面的实锤if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j]3、为什么按顺序加入中转站就不会错这个要是作业啦我就不画灵魂图示了。绝对不是懒4、动态规划①dp[k][i][j]表示从节点i到节点j允许经过的中间节点不超过k时所能获得的最短路径长度。不超过k意味着路径中除了起点i,j以外其他节点编号都小于等于k。②分治对于任意一对节点i,j当我们把允许使用的中间节点从k-1扩展到k选择是否把k作为跳板故而dp[k][i][j]取两种情况的最小值A、不经过dp[k][i][j]dp[k-1][i][j]B、经过路径分两段dp[k][i][j]dp[k-1][i][k]dp[k-1][k][j]③状态转移方程dp[k][i][j] min( dp[k-1][i][j], dp[k-1][i][k] dp[k-1][k][j] )边界条件k0无中间点。④阶段k的递推过程三位表格填充顺序k0时无中间点仅能走边。k1时{1}可以绕行节点1。k2时……kN时{1,2,...,N}可以绕行任何节点——全源最短路5、空间优化状态转移方程说的很清楚dp[k]仅依赖于dp[k-1]所以滚动吧数组直接在d[i][j]上更新就行了。for k in range(n): # 第 k 轮允许中间节点编号 ≤ k for i in range(n): for j in range(n): if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j]嗯经典DP就是好讲好学好理解一句话Floyd算法是在“路径中间点的集合”上进行递推不仅解释了算法的正确性也揭示了算法复杂度和原地更新的问题。在动态规划中我们定义dp[k][i][j]表示“允许经过编号≤k的中间节点”从松弛的视角来看在第k轮松弛开始前所有点对i,j对应的dist[i][j]当前最短路都已经是在“仅允许k-1个节点作为中间点”意义下的最优解那么第k轮要做的事情就是尝试使用节点k进行松弛。什么是尝试松弛呢就是if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j]尝试使用节点k对i,j之间的路径进行松弛。尝试松弛是Floyd算法的动作动态规划是Floyd算法的本质松弛不太好严格证明为何我把每个点都当中转站就能找到全局最短路而DP给出了单调递增集合扩张的过程可以严谨的证明当k从1到N时dist[i][j]必定收敛切全局最优。