Answers are grounded in this paper and cite their sources.
We consider the single-source shortest path (SSSP) problem: given an undirected graph with integer edge weights and a source vertex <tex-math notation="LaTeX">v</tex-math> , find the shortest paths from <tex-math notation="LaTeX">v</tex-math> to all other vertices. In this paper, we introduce a novel parallel algorithm, derived from the Bellman-Ford and Delta-stepping algorithms. We employ various pruning techniques, such as edge classification and direction-optimization, to dramatically reduce inter-node communication traffic, and we propose load balancing strategies to handle higher-degree vertices. These techniques are particularly effective on power-law graphs, as demonstrated by our extensive performance analysis. In the largest tested configuration, an R-MAT graph with <tex-math notation="LaTeX">2³⁸</tex-math> vertices and <tex-math notation="LaTeX">2⁴²</tex-math> edges on 32,768 Blue Gene/Q nodes, we have achieved a processing rate of three Trillion Edges Per Second (TTEPS), a four orders of magnitude improvement over the best published results.
No takes yet. Share an insight, caveat, or question.
Chakaravarthy et al. (2016) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: