融合路径生成过程的改进Floyd算法的最短路径问题研究
Research on the Shortest Path of the Improved Floyd Algorithm Integrating Path Generation Process
范倪圣 1胡益波 1柯锦鸿 1王佳祺 1夏小云1
作者信息
摘要
为了解决传统Floyd算法生成路径中出现的结点遗漏问题,提出三种构造路径的方法对Floyd算法进行改进.首先,使用代数方法推演了三种方法构造路径的过程,分别证明了三种方法的正确性;然后,证明了基于"递归法+后继顶点法"组合方法在增减序列存在"zz""zjz"或"jzj"其中一种子串的条件下,Floyd算法生成的路径中存在结点遗漏的情况,解答了出现结点遗漏的原因;最后,对Floyd算法的正确编写方法给出建议.实验结果表明,基于Floyd算法改进的三种构造路径的方法能够生成不遗漏结点的最短路径.
Abstract
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算法/生成路径/结点遗漏/递归法/后继顶点法Key words
Floyd algorithm/generation path/node omission/recursion method/successor vertex method引用本文复制引用
基金项目
嘉兴学院大学生研究训练(SRT)计划(2022)(8517221274)
出版年
2024
国家科技期刊平台
NSTL
万方数据