A new exact algorithm for the shortest path problem: An optimized shortest distance matrix. (August 2021)

• Record Type: Journal Article
• Authors: Yuan, Huilin; Hu, Jianlu; Song, Yufan; Li, Yanke; Du, Jie
• Is Part Of: Computers & industrial engineering. Volume 158(2021)
• Publication Date: 2021-08
• Subjects: Graph theory -- Shortest path -- Multiple pairs -- Algebraic method -- Shortest distance matrix; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2021.107407
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A new shortest distance matrix (SDM) algorithm is proposed. The SDM algorithm adopts The Power-plus Operation defined by us. The SDM algorithm can be used to solve the shortest path problem. The SDM can compute vertices independently and process them in parallel. In incomplete graphs, the efficiency of SDM algorithm is greatly improved. Abstract: The growing amount of data generated from the increasingly sophisticated network connections requires greater accuracy and higher efficiency in pinpointing the shortest paths concerned. Therefore, the earlier classical exact algorithms are no longer 100 percent suitable for large-scale data processing, for their known great time complexity during calculation. In this paper, We present an updated shortest distance matrix (SDM) algorithm. Evidence to the operation's properties is provided and the properties are used in subsequent optimizations. Compared with Dijkstra's algorithm and Floyd's algorithm, the optimized SDM algorithm with parallel mode makes a great improvement in shortening the running time. The data test shows that the new algorithm improves the efficiency in processing a large amount of data.