Research on parallelization of Floyd-Warshall algorithm
This article first analyzes the existing Floyd-Warshall algorithm and points out the problem of low execution effi-ciency and inability to run efficiently on dense graphs with large amounts of data.To solve this problem,this article studies from the perspective of parallel computing,optimizing the sequential process of performing a matrix iteration with a given insertion point in the algorithm and refreshing all the current shortest paths one by one to a synchronous refreshing process based on parallel comput-ing.This optimization reduces the time complexity of Floyd algorithm from the original cubic order to the linear order,improves the execution efficiency of the algorithm theoretically,and makes it possible for the algorithm to calculate and solve the dense graph with large amount of data smoothly.
万方数据
维普
