We present a study of multithreaded implementations of
Thorup's algorithm for solving the Single Source Shortest
Path (SSSP) problem for undirected graphs. Our implementations
leverage the fledgling MultiThreaded Graph Library
(MTGL) to perform operations such as finding connected
components and extracting induced subgraphs. To achieve
good parallel performance from this algorithm, we deviate
from several theoretically optimal algorithmic steps. In
this paper, we present simplifications that perform better in
practice, and we describe details of the multithreaded implementation
that were necessary for scalability.
We study synthetic graphs that model unstructured networks,
such as social networks and economic transaction
networks. Most of the recent progress in shortest path algorithms
relies on structure that these networks do not have.
In this work, we take a step back and explore the synergy between
an elegant theoretical algorithm and an elegant computer
architecture. Finally, we conclude with a prediction
that this work will become relevant to shortest path computation
on structured networks.
