A novel Approach to Shortest Path Problem on Distributed Graph

Abstract

Recently, the efficient of query evaluation on big graphs is an important research topic in computer science. A widely-used query is the shortest path query between two nodes in a graph, which can be evaluated on a general graph by using a few well-known algorithms such as Dijkstra, Johnson or Floyd-Warshall; however, it is nontrivial to answer this kind of query in a distributed graph. In this paper, we propose a novel approach based on the partial evaluation to solve shortest path problem between two nodes on distributed graph. We show that our algorithm can be readily implemented in the MapReduce framework, in parallel. Using a real-life data we perform experiments and show that our algorithm is scalable on large graphs on the distributed systems.