Matlab的F方法
发布时间
阅读量：
阅读量
Floyd算法思想
设矩阵A=（a_ij）m×l，矩阵B=（b_jk）l×n，定义矩阵C=A*B=（c_ij）m×n，其中c_ij=min{a_i1+b_1j，a_i2+b_2j，…，a_il+b_lj}。
设矩阵A=（a_ij）m×n，矩阵B=（b_ij）m×n，定义矩阵D=A+B=（d_ij）m×n，其中d_ij=min{a_ij，b_ij}。
借助上述两个公式来描述Floyd算法：假设距离矩阵D=（d_ij）{n×n}，当节点i与节点j之间不直接相连时，则令d_ij=∞。随后依次计算出矩阵D₂、D₃、…、D_n，其中D_n=D{n-1}*D，表示从i出发经过n步到达j的最短路径长度。S=D+D₂+D₃+…+D_n，则表示节点i到节点j的所有路径中最短的一条。每当对S进行更新时，同时对转接矩阵R进行相应的调整。
算法步骤
针对包含n个顶点的图，在已知边长为d_ij的情况下，依次计算各个n×n的W阵和R阵。前者用于记录路径长度信息，后者用于存储转接路由信息。具体操作步骤如下：
全部评论 (0)
还没有任何评论哟~