EFS: Entropy First Search for Dynamic Shortest Path Problem in Large Sparse Graphs
Quan Zhou, Hui Ying Zhao, Huijie Zhang, Shulin Tian, Zhen Liu · Journal of Computational and Theoretical Nanoscience · 2017
Searching the dynamic shortest path is a hot topic recently. In this paper we proposed a new method to solve the dynamic single source shortest paths (SSSP) problem in sparse graphs. The main contributions are three: firstly, in the preprocessing stage, we use the unreachable and unstartable characteristics to avoid most of the non-solution path search. Secondly, Entropy first search (EFS) is introduced to speed up the search process in finding the possible shortest path and then the algorithm can converges as soon as possible. In addition, the update algorithm for dynamic shortest path search is proposed for practical use. The experiments in large random sparse graphs show the efficiency and benefits of the proposed method.