融合路径生成过程的改进Floyd算法的最短路径问题研究  

Research on the Shortest Path of the Improved Floyd Algorithm Integrating Path Generation Process

作　　者：范倪圣 胡益波 柯锦鸿 王佳祺 夏小云 FAN Nisheng;HU Yibo;KE Jinhong;WANG Jiaqi;XIA Xiaoyun(Jiaxing University,Jiaxing 314001,China)

机构地区：[1]嘉兴大学,浙江嘉兴314001

出　　处：《现代信息科技》2024年第11期31-39,共9页Modern Information Technology

基　　金：2022年度嘉兴学院大学生研究训练(SRT)计划项目(8517221274)。

摘　　要：为了解决传统Floyd算法生成路径中出现的结点遗漏问题,提出三种构造路径的方法对Floyd算法进行改进。首先,使用代数方法推演了三种方法构造路径的过程,分别证明了三种方法的正确性;然后,证明了基于“递归法+后继顶点法”组合方法在增减序列存在“zz”“zjz”或“jzj”其中一种子串的条件下,Floyd算法生成的路径中存在结点遗漏的情况,解答了出现结点遗漏的原因;最后,对Floyd算法的正确编写方法给出建议。实验结果表明,基于Floyd算法改进的三种构造路径的方法能够生成不遗漏结点的最短路径。In order to solve the problem of missing nodes in the generation path of traditional Floyd algorithm,three methods of path construction are proposed to improve Floyd algorithm.Firstly,the process of constructing the path by three methods is deduced by algebraic method,and the correctness of the three methods is proved respectively.In the next section,it is proved that node omission exists in the path generated by Floyd algorithm based on the combination method of“recursion method+successor vertex method”under the condition that Increase/decrease sequence has one of the seed strings of“zz”“zjz”or“jzj”,and the reason of node omission is explained.Finally,the author gives some suggestions on how to write Floyd algorithm correctly.The experimental results show that the three methods of path construction improved by Floyd algorithm can generate the shortest path without missing nodes.

关 键 词：FLOYD算法 生成路径 结点遗漏 递归法 后继顶点法 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]