弗洛依德Floyd算法：计算任意一对顶点间的最短路径

阅读量：

A是一个n阶方阵，用于存储图中所有顶点对之间的最短路径长度。初始状态下，A即为邻接矩阵，其中A=w。

依次取k=0,1,...,n-1，并计算A[i][j]=min{A[i][j], A[i][k]+A[k][j]}，即在vi到vj的路径中依次引入v0,v1,...,vn-1，以寻找最短路径。

P[n][n]是一个二维数组，其中P[i][j]用于记录顶点i到j的最短路径中i的直接后继节点。

例如，在下图中，求解各顶点对之间最短路径的具体过程如下：

首先，需要对两个矩阵进行初始化操作，从而获得如下所示的两个矩阵（其中矩阵中的v1至v7相应调整为v0至v6）。在初始状态下，矩阵D被设定为邻接矩阵。

在P矩阵中，数值0对应v0，而数值1则对应v1..........

全部评论 (0)

还没有任何评论哟~