floyed算法的伪代码文字描述。
时间: 2023-12-14 15:34:46 浏览: 157
floyd算法代码
以下是Floyd算法的伪代码文字描述:
假设有一个带权有向图G,其邻接矩阵为D,n为顶点个数。
1. 初始化:令D0=D,即D0[i][j]表示i到j的最短路径长度的初始值为i到j的边的权值,若i和j之间没有边相连,则D0[i][j]=∞。
2. 令Dk表示从i到j只经过{1,2,...,k}中的顶点的最短路径长度,则Dk[i][j]=min{Dk-1[i][j], Dk-1[i][k]+Dk-1[k][j]}。
3. 重复执行步骤2,直到Dn为所求的最短路径长度矩阵。
其中,Dk-1[i][j]表示从i到j只经过{1,2,...,k-1}中的顶点的最短路径长度,Dk-1[i][k]+Dk-1[k][j]表示从i到j经过k的最短路径长度。
阅读全文