Finding the Minimal Cost Path in Time-Dependent Graphs

This paper proposes an efficient search to find a minimal cost path in a time-dependent graph. Current method discovers paths to the destination by expanding discovered paths originated from the source vertex. However, this blind search incurs large searching space, which lowers the query efficiency. The searching space is reduced in the following two ways. Firstly, during the search, the computation is confined within the valid time interval of each vertex to avoid useless computations. Besides, the costs of new expanded paths is computed not until the minimal cost of a path within a time interval of a vertex is correctly computed. Secondly, two searches are respectively invoked from the source vertex and the destination vertex, by which the searching space is roughly located in two small circles centered at the source and the destination. The bi-directional search stopping criteria as well as the way to regenerate the minimal cost path are discussed. The correctness of the proposed method is also theoretically proved. Finally, extensive experiments on large scale datasets confirm the efficiency of the proposed method.