最短路径-弗洛伊德算法

整理自《数据结构高分笔记》

1、算法思想

迪杰斯特拉算法可以得到从图中某一顶点到图中其余每个顶点的最短路径。如果只要求算图中任意一对顶点间的最短路径，则通常用弗洛伊德算法。

关于弗洛伊德算法的原理，我们直接通过一个例子来体会一下：

上图中对应的邻接矩阵为：

初始时要设置两个矩阵A和Path，A用来记录当前已经求得的任意两个顶点的最短路径长度，Path用来记录当前两顶点间最短路径上要经过的中间顶点。

初始时：A和Path如下所示：

第一步
以0作为中间点，参照上一步矩阵的结果，检测所有结点对，假设当前所检测的顶点对为（i，j），如果A[i][j]>A[i][0] + A[0][j],则将A[i][j]改为A[i][0] + A[0][j]的值，并将Path[i][j]改为0.经过本次检测和修改，所得矩阵如下：

第二步
以1为中间节点，参照上一步矩阵的结果，检测所有结点对，其中有：A[0][2]>A[0][1] + A[1][2]=9，所以将A[0][2]改为9，Path[0][2]改为1:

第三步
以2为中间节点，参照上一步矩阵的结果，检测所有结点对，进行修改。

第四步
以3为中间节点，参照上一步矩阵的结果，检测所有结点对，进行修改。

经过上面的步骤，得到的最终的矩阵为：

由矩阵A可以得到图中任意两点之间的最短路径长度，以及最短路径所经过的结点。