About this document
Parallel Shortest Path Algorithm Study by hectorjazz is a document available to read on EtoBox.
This document presents an experimental study of a parallel algorithm called Δ-stepping for solving the single source shortest path problem on large-scale graphs. The algorithm was implemented on the Cray MTA-2 parallel computer and tested on graph instances with billions of vertices and edges. The implementation showed near-linear speedup on sparse graphs, solving problems orders of magnitude larger than previous studies and obtaining speedups of up to 30 times on 40 processors for random graphs. This study
- Author
- hectorjazz
- Language
- EN