Single-source shortest paths with the parallel boost graph library
Nick Edmonds, Alex Breuer, Douglas Gregor, Andrew Lumsdaine · DIMACS series in discrete mathematics and theoretical computer science · 2009
The Parallel Boost Graph Library (Parallel BGL) is a library of graph algorithms and data structures for distributed-memory computation on large graphs. Developed with the Generic Programming paradigm, the Parallel BGL is highly customizable, supporting various graph data structures, arbitrary vertex and edge properties, and different communication media. In this paper, we describe the implementation of two parallel variants of Dijkstra’s single-source shortest paths algorithm in the Parallel BGL. We also provide an experimental evaluation of these implementations using synthetic and real-world benchmark graphs from the 9 th DIMACS Implementation Challenge.