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.
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: 20 Nov 2017 *