ex-FTCD: A novel mapreduce model for distributed multi source shortest path problem

摘要

Computing the all pair shortest paths in a graph is a widely used solution, but a time-consuming process too. The popularly used conventional algorithms rely solely on the computing capability of the CPU, but fail to meet the demand of real-time processing and mostly do not scale well for larger data. In this paper, we propose the ex-FTCD (extending Full Transitive Closure with Dijkstra's) algorithm for finding the all pair shortest path by merging the features of the greedy technique in Dijkstra's single source shortest path method and the transitive closure property. Experiments show that the process improves computing speed and is more scalable. We re-designed the algorithm for the parallel execution and implemented it in mapreduce on Hadoop that supports the conventional map/reduce jobs. This work also includes the implementation on Spark that supports the in-memory computational capability which uses Random Access Memory for computations. The experiments show that the numbers of iterations are relatively small for even large networks.