Title: A fast search strategy to optimise path founding in big data graph computing environments

Authors: Wentian Qu; Dawei Sun

Addresses: School of Information Engineering, China University of Geosciences, Beijing 100083, China ' School of Information Engineering, China University of Geosciences, Beijing 100083, China

Abstract: In big data graph computing environments, the shortest path problem is very important and widely applied in various scenarios. But sometimes, in order to find the shortest path, it always entails a lot of cost. So, weighing the various aspects of the problems, it's a good choice to find optimal path. In this paper, an improved A-star algorithm is proposed to define the optimal path. A-star algorithm has two kinds of parameters named actual cost and estimated cost and the second one plays an important part in the algorithm. Based on the traditional A-star algorithm, this paper will propose new parameters and improved heuristic function to enhance the performance of the A-star algorithm. Compared with the traditional A-star algorithm, the simulation experiment shows that the improved A-star algorithm runs at high efficiency. Two factors which affect the best situation are also discussed in the end of this paper.

Keywords: improved A-star algorithm; optimal path; estimated cost; heuristic function; graph computing; big data.

DOI: 10.1504/IJWMC.2017.088083

International Journal of Wireless and Mobile Computing, 2017 Vol.13 No.2, pp.139 - 143

Received: 11 Apr 2017
Accepted: 07 May 2017
Published online: 21 Nov 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article