Floyd算法的一点讨论

按照经典路径，很多人学习最短路算法时学习的可能都是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] )

边界条件k=0：无中间点。

④阶段k的递推过程（三位表格填充顺序）

k=0时，无中间点，仅能走边。

k=1时，{1}，可以绕行节点1。

k=2时，……

k=N时，{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]必定收敛切全局最优。