  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.
