Floyd-Warshall算法过程中矩阵计算方法—十字交叉法

先来简单分析下,由于矩阵中对角线上的元素始终为0,因此以k为中间点时,从上一个矩阵到下一个矩阵变化时,矩阵的第k行,第k列和对角线上的元素是不发生改变的（对角线上都是0，因为一个顶点到自己的距离就是0，一直不变；而当k为中间点时，k到其他顶点（第k行）和其他顶点到k（第k列）的距离是不变的）。

因此每一步中我们只需要判断4*4-3*4+2=6个元素是否发生改变即可,也就是要判断既不在第k行第k列又不在对角线上的元素。具体计算步骤如下：以k为中间点（1）“三条线”：划去第k行，第k列，对角线（2）“十字交叉法”：对于任一个不在三条线上的元素x，均可与另外在k行k列上的3个元素构成一个2阶矩阵，x是否发生改变与2阶矩阵中不包含x的那条对角线上2个元素的和有关，若二者之和小于x，则用它们的和替换x，对应的Path矩阵中的与x相对应的位置用k来替代。。。下面来具体看高分笔记上面的那个题目吧。。。。

详细图解：