论文标题
黎明：对于未加权图上最短路径问题的矩阵操作优化算法
DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted Graphs
论文作者
论文摘要
最短的路径问题是图理论中的基本挑战，具有广泛的潜在应用。基于基质乘法的算法表现出极好的并行性和可扩展性，但受高记忆消耗和算法复杂性的约束。传统的最短路径算法受到优先队列的限制，例如BFS和Dijkstra算法，使其平行性的改善成为焦点问题。我们提出了一种矩阵操作优化算法，该算法提供了改进的并行性，减少时间复杂性和降低的存储器消耗。 The novel algorithm requires $O(E_{wcc}(i))$ and $O(S_{wcc} \cdot E_{wcc})$ times for single-source and all-pairs shortest paths problems, respectively, where $S_{wcc}$ and $E_{wcc}$ denote the number of nodes and edges included in the largest weakly connected component in graph.为了评估新算法的有效性，我们使用Suitesparse Matrix Collection和Gunrock Bench Marks数据集的图进行了测试。我们的算法优于Gunrock和Gap（以前的最先进的解决方案）的BFS实现，分别达到平均速度为3.769 $ \ times $ $和9.410 $ \ times $。
The shortest paths problem is a fundamental challenge in graph theory, with a broad range of potential applications. The algorithms based on matrix multiplication exhibits excellent parallelism and scalability, but is constrained by high memory consumption and algorithmic complexity. Traditional shortest paths algorithms are limited by priority queues, such as BFS and Dijkstra algorithm, making the improvement of their parallelism a focal issue. We propose a matrix operation-optimized algorithm, which offers improved parallelism, reduced time complexity, and lower memory consumption. The novel algorithm requires $O(E_{wcc}(i))$ and $O(S_{wcc} \cdot E_{wcc})$ times for single-source and all-pairs shortest paths problems, respectively, where $S_{wcc}$ and $E_{wcc}$ denote the number of nodes and edges included in the largest weakly connected component in graph. To evaluate the effectiveness of the novel algorithm, we tested it using graphs from SuiteSparse Matrix Collection and Gunrock benchmark dataset. Our algorithm outperformed the BFS implementations from Gunrock and GAP (the previous state-of-the-art solution), achieving an average speedup of 3.769$\times$ and 9.410$\times$, respectively.
