floyed一个总是讲不清楚的算法
2021-03-19 00:27
标签：过程 不清楚 一个 代码 修改 jpg 顺序 http 讲解 floyed一个总是讲不清楚的算法 标签：过程 不清楚 一个 代码 修改 jpg 顺序 http 讲解 原文地址：https://www.cnblogs.com/caterpillor/p/13765029.html
在上述讲解中，举例所有点先经过1号点，再经过2号点，得到一个经过1、2号点的最短路，比如4-3最短路是10。
那么问题来了，讲解中，经过1、2、3...n号点是按照顺序经过的，那么如果先枚举所有点经过2号点，再经过1号点，得到的最短路和上述方式结果一样么？
比如是这样的。
我们可以模拟这个过程，那么将得到先通过1号点修改了2-3的最短路，在代码第一行。然后求4-3最短路时，经过2号点，而2-3在经过1号点时已经被修改成了当前最优。因此经过的点的顺序是没有影响的。只经过1号点
**f[2][3] = min(f[2][1] + f[1][3], f[2][3]) = 5**
f[2][4] = min(f[2][1] + f[1][4], f[2][4]) = ∞
f[3][2] = min(f[3][1] + f[1][4], f[3][2]) = ∞
f[3][4] = min(f[3][1] + f[1][4], f[3][4]) = 1
f[4][2] = min(f[4][1] + f[1][2], f[4][2]) = 5
f[4][3] = min(f[4][1] + f[1][3], f[4][3]) = ∞
再累计经过号点求最短
f[1][3] = min(f[1][2] + f[2][3], f[1][3]) = 3
f[1][4] = min(f[1][2] + f[2][4], f[1][4]) = ∞
f[3][1] = min(f[3][2] + f[2][1], f[3][1]) = ∞
f[3][4] = min(f[3][2] + f[2][4], f[3][4]) = 1
f[4][1] = min(f[4][2] + f[2][1], f[4][1]) = 7
**f[4][3] = min(f[4][2] + f[2][3], f[4][3]) = 5 + 5**