A novel Approach to Shortest Path Problem on Distributed Graph

  • Nguyen Thi Huyen Hanoi University of Science and Technology
  • Pham Dang Hai Hanoi University of Science and Technology
Keywords: Graph Querying, MapReduce, Shorstest Path, Distributed Graph, Partial Evaluation.

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.

Published
2020-04-21
How to Cite
Nguyen Thi Huyen, & Pham Dang Hai. (2020). A novel Approach to Shortest Path Problem on Distributed Graph. UTEHY Journal of Science and Technology, 9, 56-62. Retrieved from https://tapchi.utehy.edu.vn/index.php/jst/article/view/302