Based Approach to Improve the All-Pair Shortest Path Computation

Abstract

This paper presents the development of a centralized algorithm for finding the shortest path between all pairs of vertices on a graph, utilizing the basic structure of the Floyd-Warshall sequential algorithm. The proposed algorithm leverages multiple processors to compute the shortest path between all vertex pairs, with one processor taking the central role in data management. This central processor divides the workload, assigning tasks to other processors for parallel computation of the shortest paths. The algorithm is implemented in Java and tested on both MapReduce and MPI architectures, running on the computer system at Hanoi National University of Education (ccs1.hnue.edu.vn). The study utilizes traffic road datacollected from Da Nang City, Vietnam, providing real-world input for evaluating the algorithm's performance on large-scale datasets. The results demonstrate the efficiency of the algorithm in a distributed environment, highlighting its potential for solving shortest path problems in real-world urban networks.