算法研究：最短路径之弗洛伊德算法

为了能讲明白弗洛伊德(Floyd)算法的主要思想，我们先来看最简单的案例。图7-7-12的左图是一个简单的3个顶点的连 通网图。

我们先定义两个二维数组D[3][3]和P[3][3]， D代表顶点与顶点的最短路径权值和的矩阵。P代表对应顶点的最短 路径的前驱矩阵。在未分析任何顶点之前，我们将D命名为D(-1)，其实它就是初始图的邻接矩阵。将P命名为P(-1), 初始化 为图中的矩阵。

首先我们来分析，所有的顶点经过v0后到达另一顶点的最短路径。因为只有3个顶点，因此需要查看 v1->v0->v2，得到

D(-1)[1][0] + D(-1)[0][2] = 3。D(-1)[1][2]表示的是v1->v2的权值为5，我们发现 D(-1)[1][2] > D(-1)[1][0] + D(-1)[0][2] ,通俗话来说就是

v1->v0->v2 比v1->v2距离还要近。所 以我们就让 D(-1)[1][2] = D(-1)[1][0] + D(-1)[0][2] = 3, 同样地D(-1)[2][1] = 3, 于是就有了D(0)矩阵。因为有变 化，所以P矩阵对应的P(-1)[1][2]和P(-1)[2][1]也修改为当前中转的顶点v0的下标0, 于是就有了P(0)。也就是说

接下来，也就是在D(0)和P(0)的基础上继续处理所有顶点经过v1和v2后到达另一顶点的最短路径，得到D(1)和P(1)、D (2)和P(2)完成所有顶点到所有顶点的最短路径计算工作。

首先我们针对图7-7-13的左网图准备两个矩阵D(-1)和P (-1)，D(-1)就是网图的邻接矩阵，P(-1)初设为P[i][j]=j 这样的矩阵。主要用来存储路径。