NDLI: IBAS: Index Based A-Star

Content Provider	Directory of Open Access Journals (DOAJ)
Author	Yan Li Hongyan Zhang Huaizhong Zhu Jianwei Li Wenjie Yan Youxi Wu
Abstract	The A-star algorithm is an efficient classical algorithm for solving the shortest path problem. The efficiency of the algorithm depends on the evaluation function, which is used to estimate the heuristic value of the shortest path from the current vertex to the target. When the vertex coordinates are known, the heuristic value of the shortest path is usually generated by the distance. In this paper, we present an Index Based A-Star algorithm (IBAS), which aims to solve the shortest path problem in a weighted directed acyclic graph with unknown vertex coordinates. This paper constructs three indexes for each vertex, i.e., the earliest arrival index, reverse earliest arrival index, and latest arrival index. We can compute the lower bound and the upper bound of the shortest distance from the source vertex to the target based on the three indexes and prune the intermediate vertices which are not in shortest path according to the lower and upper bounds. The IBAS algorithm not only makes use of the earliest arrival index to construct the evaluation function of the A-star algorithm but also utilizes the three indexes to prune useless vertices, so as to improve the performance of the algorithm. Compared with the A-star algorithm, the additional time complexity and space complexity of the IBAS algorithm are O(IV I + IEI) and O(IV I), respectively. A real road network and benchmark datasets with large-scale network are selected to verify the performance of IBAS. Experimental results verify the effectiveness of the proposed algorithm.
e-ISSN	21693536
DOI	10.1109/ACCESS.2018.2808407
Journal	IEEE Access
Volume Number	6
Language	English
Publisher	IEEE
Publisher Date	2018-01-01
Publisher Place	United States
Access Restriction	Open
Subject Keyword	Electrical Engineering. Electronics. Nuclear Engineering Shortest Path A-star Algorithm Pruning Strategy Index
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in