Floyd算法的推广

Extensionof Floydalgorithm

最短路径问题在很多现实问题中都有着至关重要的地位,研究了Floyd算法在平面网格节点最短路径问题中的推广应用。首先介绍算法的基本思想、基本原理和基本步骤;其次采用对比的方法,算法推广的基本思想,原理和步骤。讨论算法原理的距离矩阵与位置矩阵,距离矩阵由2维矩阵推广到4维矩阵,表示节点到节点的距离;算法的位置矩阵由一个2维的位置矩阵,推广到两个4维矩阵,分别表示节点的横纵坐标。两种算法计算二维平面网格节点最短路径问题时,采用一维Floyd算法计算时,邻接矩阵给出相对复杂;由例2可知,二维Floyd算法可直接应用于山地修路问题中,比一维Floyd算法计算更简便。

The shortest path problem plays an important role in many practical problems.This paper studies the popularization and application of Floyd algorithm in the shortest path problem of planar mesh nodes.Firstly,the basic idea,principle and steps of the algorithm are introduced;Secondly,the comparative method is used to popularize the basic idea,principle and steps of the algorithm.The distance matrix and position matrix of the algorithm principle are discussed.The distance matrix is extended from two-dimensional matrix to four-dimensional matrix,which represents the distance from node to node.The location matrix of the algorithm is extended from a two-dimensional location matrix to two four-dimensional locations,respectively representing thehorizontal and vertical coordinates of nodes.When the two algorithms calculate the shortest path problem of two-dimensional plane grid nodes,the adjacency matrix is relatively complex when the one-dimensional Floyd algorithm is used.As can be seen from Example 2,the two-dimensional Floyd algorithm can be directly applied to the mountain road construction problem,and the calculation is simpler than the onedimensional Floyd algorithm.