MapReduce Algorithm for Single Source Shortest Path Problem
CSED, MNNIT Allahabad, Prayagraj (India), Praveen Kumar, Anil Kumar Singh · International Journal of Computer Network and Information Security · 2020
Computing single source shortest path is a popular problem in graph theory, extensively applied in many areas like computer networks, operation research and complex network analysis.SSSP is difficult to parallelize efficiently as more parallelization leads to more work done by any algorithm.MapReduce is a popular programming framework for large data processing in distributed and cloud environments.In this paper, we have proposed MR-DSMR, a Map reduce version of Dijkstra Strip-mined Relaxation (DSMR) algorithm and MR3-BFS algorithms.We have compared the performance of both the algorithms with BFS.It is observed that MR-DSMR takes lesser communication and computation time compared to existing algorithms.