Publication Type:

Conference Paper

Source:

2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), IEEE, Udupi, India (2017)

URL:

https://ieeexplore.ieee.org/abstract/document/8126138

Keywords:

All pair shortest path, Dikjstra's algorithm, distributed system, transitive closure

Abstract:

Due to the explosion of data from various sources, data analytics is found to be difficult using the CPU alone. For huge networks, the most popular graph algorithms using a single processor failed to accomplish this task. Hence the need of algorithms that have higher processing capabilities became dominant. Graph analytics is gaining importance in the realm of data analysis due to the advantages over other conventional analytical methods. All pair shortest path problem or path-finding problem has applications in various fields. Finding the all pair shortest path in a graph is computationally complex and time consuming in the case of large networks. In this paper, we propose a map reduce approach using the in-memory computation for finding the all pair shortest path using the transitive closure property and the greedy technique in Dijkstra's single source shortest path method. In order to overcome the scalability issues in the network representation, we use a tuple based network representation. The performance of the proposed method is proved experimentally.

Cite this Research Publication

S. Vaid, Salih, R., Gayathri, R. G., and Jyothisha J. Nair, “All pair shortest path using distributed architectures”, in 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Udupi, India, 2017.