基于Floyd算法的多重最短路问题的改进算法

摘要

路径分析是网络分析最基本的问题,其核心是对最短路径的求解.Floyd算法是一种求取最短路的经典算法.分析发现,两点间可能存在多条权重相同的最短路径,而这一点Floyd算法没有涉及.以无向联通图为研究对象,设计了基于Floyd求解多重等价最短路算法,并分析计算了一个实际算例.计算结果表明,基于Floyd的多重等价最短路算法可以有效解决多重等价最短路问题.%Find the shortest path is the core of the path analysis,which is the fundamental problem of the network analysis.Floyd algorithm is one of the most classical algorithms to solve the shortest path problem.Through analyzing practical problems,there maybe exist multiple shortest paths with the same weight that the Floyd algorithm are not addressed.This paper designed the multi-shortest paths algorithm for undirected graph based on Floyd algorithm and offered an example to exam the correctness of the algorithm.The experimental results show that the algorithm can effectively solve the problem of muti shortest paths.