Implementation of IBAS: Index Based A-Star proposed by Yan Li, Hongyan Zhang, Huaizhong Zhu, Jianwei Li, Wenjie Yan and Youxi Wu (Member, IEEE). The Research Paper aims to solve the shortest path problem in a weighted directed acyclic graph with unknown vertex coordinates and compared this algorithm with IBAS-S (which uses only static pruning), A-Star and Dijsktra algorithms to find its working efficiency.
The main contributions of this study are threefold:
- Proposed methods for constructing the earliest arrival index, reverse earliest arrival index, and latest arrival index in a weighted DAG.
- Presented an index-based A-star algorithm, IBAS, which uses the earliest arrival index to construct the evaluation function of the A-star algorithm, and also employs the above three indexes to achieve effective pruning.
- Through extensive experiments, demonstrated that IBAS can effectively boost the speed of traditional algorithms, and the efficiency of the reachability cost index is high.
- Enter the number of vertices: 23
- Enter the number of edges: 27
- Enter the edges of DAG: 0 1 2 1 2 2 2 3 4 3 4 3 4 5 6 4 6 2 4 9 3 6 7 2 7 8 3 9 8 8 14 4 5 14 9 4 11 3 2 10 11 4 10 12 2 12 13 1 13 14 1 21 14 3 14 18 5 20 21 2 19 20 2 19 18 9 19 22 2 22 17 15 18 15 2 15 16 3 16 17 3
