弗洛伊德算法 简便理解(大白话)

弗洛伊德算法 简便理解(大白话)
弗洛伊德算法 简便理解(大白话)

参数说明

D矩阵

D 矩阵为各个顶点之间的距离(权)
如果两个顶点之间没有弧,则为无穷大
0代表自己和自己

D(-1) 表示初始状态下的带权的有向图之间的距离,即每个顶点之间的距离

D(0) 表示各个顶点之间的距离要从初始态变化成经过顶点0后的距离,值得注意的是就像我在图上画的,包含0的行和列的数值不需要变化(因为还是顶点0到某个顶点)

需要在D(0)中变化的即是:(以0、1、无穷、4为横轴,以0、无穷、3、无穷为纵轴)上的元素两两相加与D(-1) 中相同的位置做大小比较,如果两者之和小于原来的距离则替换,如果两者之和比原来的距离大则不变
所以可以解释图中画圆圈的5和8被4(4=3+1)和7(7=3+4)替换的原因了

依次类推可以得出D(1) 中画三角的元素(1的那一行和1的那一列元素始终不变)

P矩阵

P矩阵:最短路径上顶点Vj的前一个顶点的序号
-1代表两者之间没有弧同上面的无穷

如P-1 中都是初始状态,如第一行的两个0代表0到1的最短路径是由0指过来的,0到3的最短路径是由0指过来的

P0 中开始做变化,变化的元素就是上面距离改变了的元素如5、8变成了4、7,所以下面对应的2、2变成0、0。即就是2到1的最短路径(2->0->1,所以是由0指过来的)变成了0,2到3的最短路径(2->0->1,所以)变成了0

依次类推的出后序