用于计算图中各个顶点之间的最短路径
稍微对概念做个梳理:
弗洛伊德是三层循环,第一层是中转点,第二层是起点,第三层是终点
弗洛伊德是一种DP,简单来说,当我们只在考虑i、j和k三点时,i到k的最短距离应该是
min(Dijk, Dik)
,这里解释下,Dijk
是从i出发经过j最后到达k的距离,Dik
则是从i出发直接到达k的距离。
弗洛伊德算法的实现:弗洛伊德通过对两个矩阵的维护来实现最后的结果,其中第一个矩阵是记录点i和点j之间距离的距离矩阵,第二个矩阵则是记录点i到点j之间中转的点k的中转点矩阵。
为什么说是各个顶点之间的最短路径呢?因为从最后的两个表里面,可以得到所有点和点之间的最短路径。
代码不上了