Floyed理解
Floyd算法的本质是动态规划，其转移方程为f(k,i,j) = min(f(k-1,i,j), f(k-1,i,k)+f(k-1,k,j) )。
f(k-1,i,j)表示经过前k-1个点
f(k-1,i,k)+f(k-1,k,j)表示经过k这个点
f(k,i,j)表示路径除开起点i与终点j，只经过前k个点中的某些点，从i到j的最小值。
要计算该值，只需考虑最短路通过k的情况和最短路不通过k的情况这两种情况即可。 将通过最初的k-1点中的几个点。
由于k要从k-1转移而来，自然k为最外层的循环然后经过状态压缩(类似背包问题)，我们熟悉的f(I，j )=min ) I，j )，f ) I，k ) f ) k，j ) )
其次是Floyd算法的更新过程。 总结其更新过程，实际上，每当要在各对节点Vv与Vw之间插入节点Vk时，只要在插入节点后能够缩短Vv与Vw之间的路径，就进行1次更新，否则不进行更新。
那么，为什么用这样的规则更新会找到节点对之间的最短路径呢？ 在这里举例说明的话，应该可以清楚地说明这个问题。 假设您事先知道从节点V2到V5的最短路径为V2V4V9V7V5。
首先，在初始化的过程中，获得了(d )2) )9)，(d ) )5)，(d ) )2)，以及(p ) )9)，(p ) )5)
在步骤2中，根据Floyd算法进行迭代，反复到k为4时，在V2和V9之间插入V4后，V2和V9之间的路径长度达到历史最低点，(d ) [2][9] ) d ) [2][4] )
重复步骤3，直到k变为7，V9和V5之间的路径长度达到历史最低点，(d ) ((9) )5)为(d ) ) )7) ) )5)，(p ) )9)5)更新为7
反复进行步骤4，直到k变为9，则V2和V5之间的路径长度达到历史最低点，(d ) )2) )5)是) d ) )9) )5) ) p )5) )5)5)更新为9 )之后
现在计算出了V2和V5之间的最短路径的长度，如何找到这条路径的轨迹？ 其实是根据*P来推定的。 在上面的示例中，假设打印V2和V5之间的最短路径的轨迹。 首先，得知(p ) (2) )5)=9，初步确定轨迹为V2V9V5。 根据[*p][2][9]=4且[*p][9][5]=7，初步确定轨迹为V2V4V9V7V5。 [*p][2][4]=2，*p][4][9]=4，*p][9][7]=9，*p][7][5]=7可以确定不需要添加新节点
浮动主题推荐：
【P1119】灾后重建-洛谷
https://www.Luo gu.org/problem/show？ pid=1119
【P1078】文化之旅-洛谷
https://www.Luo gu.org/problem/show？ pid=1078
转载于：https://www.cn blogs.com/Renyi-fan/p/7431556.html