Floyd算法的推广_魏玉华.pdf

115第 17 卷 第 4 期2022 年 12 月贵阳学院学报（自然科学版）（季刊）JOURNAL OF GUIYANG UNIVERSITY Natural Sciences（Quarterly）Dec.2022Vol.17No.4摘 要：最短路径问题在很多现实问题中都有着至关重要的地位，研究了 Floyd 算法在平面网格节点最短路径问题中的推广应用。首先介绍算法的基本思想、基本原理和基本步骤；其次采用对比的方法，算法推广的基本思想，原理和步骤。讨论算法原理的距离矩阵与位置矩阵，距离矩阵由 2 维矩阵推广到 4 维矩阵，表示节点到节点的距离；算法的位置矩阵由一个 2 维的位置矩阵，推广到两个 4 维矩阵，分别表示节点的横纵坐标。两种算法计算二维平面网格节点最短路径问题时，采用一维 Floyd 算法计算时，邻接矩阵给出相对复杂；由例 2 可知，二维 Floyd 算法可直接应用于山地修路问题中，比一维 Floyd 算法计算更简便。关键词：计算数学；最短路径；推广的 Floyd 算法；MATLAB中图分类号：TP3-05；O224 文献标识码：文章编号：1673-6125（2022）04-0115-05Extensionof FloydalgorithmWEI Yu-hua，XIE Xiao-jun，XUE Shen-fang（College of general education，Guangzhou College of Technology and Business，Guangzhou 510850，Guangdong，China）Abstract: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 thebasic 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 one-dimensional Floyd algorithm.Keywords:Computational mathematics;Shortest path;Generalized Floyd algorithm;MATLABFloyd 算法的推广魏玉华，谢小军，薛申芳（广州工商学院 通识教育学院，广东 广州 510850)收稿日期2022-10-11基金项目项目类型“新工科背景下线性代数课程思政元素融入研究与实践”（项目编号：ZC20211147）。作者简介魏玉华，女，福建三明市人，讲师、硕士。主要研究方向：统计分析。谢小军，男，湖南衡阳人，讲师、硕士生。主要研究方向：预测和决策分析。薛申芳，男，河北威县人，教授、博士。主要研究方向：应用数学、信息技术、卫星自主导航。Floyd 算法是图论中任意两点最短路问题的一种算法。该算法计算时要求节点排列是一维排序，当在计算二维平面网格节点最短路径问题时，必须将二维节点排序转化成一维节点（这里称为一维 Floyd 算法），在通常情况下节点个数很多，导致计算上有很大困难。该文欲考虑对一维 Floyd算法进行推广，即把距离矩阵与位置矩阵推广到二维节点，使用Floyd算法（称为二维Floyd算法），DOI:10.16856/ki.52-1142/n.2022.04.004116贵阳学院学报（自然科学版）（季刊）17 卷直接应用计算二维平面网格节点最短路径。此类问题，应用二维 Floyd 算法比一维 Floyd 算法更加便捷，容易编程和计算。1 一维Floyd算法记GV E=(),：表示无向图；v：表示无向图中的坐标点；e：表示无向图中的边；ev viii()=()-1i1,2,k：表示边ei是点vi1与点vi之间的边；Wv vk0：表示顶点与边相互交错且 ev viii()=-1 （i=1,2,K）的有限非空序列wv e v eve vkkk=()0 1 1 21称为一条从v0到vk的通路；Pv vk0：表示边与顶点均不重复的通路称为路径；P u v(,)：表示是赋权图G中从u到v的路径；w Pw ee E P()()()=：表示路径P的权；P u v*(,)：表示在赋权图G中，从节点u到节点v的具有最小权的路；Dv()：表示迭代v次后的带权邻接矩阵；Rv()：表示迭代v次后的带权距离矩阵。一维 Floyd 算法是求任意两点最短路的一种常用算法，该算法的基本思想是直接在图的带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵D()1，D()2，Dv()，使最后得到的矩阵Dv()称为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径1；该算法的基本原理和基本步骤是：距离矩阵的初值用带权邻接矩阵W来表示，即DdWijv v()()()00=；Ddijv v11()()=()，其中ddddijijij()()()()min,101010=+，dij()1是从vi到vj只许以v1作为中间点的路径最短路的长度；Ddijv v22()=()，其 中ddddijijij()()()()min,212121=+，dij()2是从vi到vj的只许以v1，v2作为中间点的路径最短路的长度；Ddvijvv v()()()=，其 中ddddijvijvivvvjv()()()()min,=+111，dijv()是从vi到vj的只许以v1，v2，vv作为中间点的路径中最短距离的长度，即使从vi到vj中间可插入任何顶点的路径中最短路的长度，因此Dv()是距离矩阵2。求路径矩阵的方法是：在建立距离矩阵的同时可建立路径矩阵R，Rrijv v=()，rij的含义是从vi到vj的最短路径过点号为rij的点。Rrijv v()()()00=，rjij()0=，每求得一个Dk()时，按下列方式产生相应新的Rk()：，即当vk被插入任何两点间的最短路径时，被记录在Rk()中，依次求Dv()时，求得Rv()，可由Rv()来查找任何点对之间最短路径3。若rpijv()=1，则点p1是点i到点j的最短路的下一个点，然后用同样的方法再继续查找。向点 j 追溯得：rpp jv12()=，rpp jv23()=，rjp jvm()=，则由点 i 到 j 的最短路径为：i p1 p2 p3pm j.算法基本步骤是：D(i,j):i 到 j 的距离，R(i，j)：i到 j 之间的插入点，输入带权邻接矩阵 W，然后赋权值：对所有 i，j，d(i，j)w(i，j)，r(i，j)j，k 1；更新 d(i，j)，r(i，j)：对所有 i，j，若d i kd k jd i j(,)(,)(,)+，则d i jd i kd k j r i jk(,)(,)(,),(,)+；若kv=，停止；否则kk+1，转上述更新4。2 Floyd 算法推广（二维 Floyd 算法）下面假设节点为坐标二维平面上的网格节点，边为平面上坐标点与坐标点之间的距离。在图的带权邻接矩阵中用插入顶点的方法构造出v个矩阵D()1，D()2，Dv()，使最后得到的矩阵Dv()称为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径，将佛勒易得算法就节点排序方面从一维排序推广到二维排序，邻接矩阵也从二维矩阵推广到四维矩阵5。算法基本原理为：带权邻接矩阵为四维邻接矩阵，W中元素W i j m n(,)表示从网格节点(,)i j到节点(,)m n的距离。如W 11 2 2,()表示点(,)11到点(,)2 2的距离，W(,)2 2 11表示点(,)2 2到点(,)11的距离。求距离矩阵的方法：把带权邻接矩阵W作为距离矩阵的初值，即DdWijmnv v v v()()()00=。Ddijmnv v v v()()()11=，其中ddddijmnijmnijmn()()()()min,10110110=+，dijmn()1是从vij到vmn的只允许以v11作为中间点的路径最短路的长度；Ddijmnv v v v()()()22=，其中ddddijmnijmnijmn()()()()min,2121221=+2，dij()2是从vij到vmn的只允许以v11，v22作为中间点的路径最短路的长度；Ddvijmnvv v v v()()()=，其中ddddijmnvijmnvijvvvvvmnv()()()()min,=+111，1174 期魏玉华等 Floyd 算法的推广dijv()是从vij到vmn的只允许以v11，v22，vvv作为中间点的路径中最短距离的长度，即使从vij到vmn中间可插入任何顶点的路径中最短路的长度，因此Dv()是距离矩阵。路径矩阵为R i j m nmR i j m nn12(,)(,)=。求路径矩阵的方法是在建立距离矩阵的同时可建立路径矩阵R R1,2RrRrijmnv v v vijmnv v v v12=()()，rijmn的含义是从vij到vmn的最短路径过点为rijmn的点的横坐标，rijmn的含义是从vij到vmn的最短路径过点为rijmn的点的纵坐标。RrRrrijmnv v v vijmnv v v vi12()()()()()()0000=j jmnijmnirj()()00=，。每求得一个Dk()时，按下列方式产生相应新的 ，即当vkl被插入任何两点间的最短路径时，被记录在RRkk12()()中，依次求Dv()时，求得RRkk12()()，可由RRkk12()()来查找任何点对之间最短路径。查找路径的方法是：若=rprqijmnvijmnv()()11，则点（p1，q1）是点(,)m n到点(,)i j的最短路的下一个点，