－115－第17卷第4期2022年12月贵阳学院学报（自然科学版）（季刊）JOURNALOFGUIYANGUNIVERSITYNaturalSciences（Quarterly）Dec.2022Vol.17No.4摘要：最短路径问题在很多现实问题中都有着至关重要的地位，研究了Floyd算法在平面网格节点最短路径问题中的推广应用。首先介绍算法的基本思想、基本原理和基本步骤；其次采用对比的方法，算法推广的基本思想，原理和步骤。讨论算法原理的距离矩阵与位置矩阵，距离矩阵由2维矩阵推广到4维矩阵，表示节点到节点的距离；算法的位置矩阵由一个2维的位置矩阵，推广到两个4维矩阵，分别表示节点的横纵坐标。两种算法计算二维平面网格节点最短路径问题时，采用一维Floyd算法计算时，邻接矩阵给出相对复杂；由例2可知，二维Floyd算法可直接应用于山地修路问题中，比一维Floyd算法计算更简便。关键词：计算数学；最短路径；推广的Floyd算法；MATLAB中图分类号：TP3-05；O224文献标识码：Ａ文章编号：1673-6125（2022）04-0115-05ExtensionofFloydalgorithmWEIYu-hua，XIEXiao-jun，XUEShen-fang（Collegeofgeneraleducation，GuangzhouCollegeofTechnologyandBusiness，Guangzhou510850，Guangdong，China）Abstract:Theshortestpathproblemplaysanimportantroleinmanypracticalproblems.ThispaperstudiesthepopularizationandapplicationofFloydalgorithmintheshortestpathproblemofplanarmeshnodes.Firstly，thebasicidea，principleandstepsofthealgorithmareintroduced;Secondly，thecomparativemethodisusedtopopularizethebasicidea，principleandstepsofthealgorithm.Thedistancematrixandpositionmatrixofthealgorithmprinciplearediscussed.Thedistancematrixisextendedfromtwo-dimensionalmatrixtofour-dimensionalmatrix，whichrepresentsthedistancefromnodetonode.Thelocationmatrixofthealgorithmisextendedfromatwo-dimensionallocationmatrixtotwofour-dimensionallocations，respectivelyrepresentingthehorizontalandverticalcoordinatesofnodes.Whenthetwoalgorithmscalculatetheshortestpathproblemoftwo-dimensionalplanegridnodes，theadjacencymatrixisrelativelycomplexwhentheone-dimensionalFloydalgorithmisused.AscanbeseenfromExample2，thetwo-dimensionalFloydalgorithmcanbedirectlyappliedtothemountainroadconstructionproblem，andthecalculationissimplerthantheone-dimensi...
