Fast Approximate Algorithm for the Single Source Shortest Path with Lazy Update

摘要

In this paper, we propose a fast approximate algorithm of the Dijkstra algorithm which solves the single source shortest path problem(SSSP). In the conventional Dijkstra algorithm, one node with the minimum tentative distance is selected from unvisited nodes, and the tentative distances of its adjacent nodes are relaxed. In this method, its optimality is guaranteed by utilizing the fact that the tentative distance of the selected node will not be updated any more. However, there may be several nodes whose tentative distance will be updated. In this paper, we reduce the computation time by using the Lazy update method which selects all of these nodes and determines their distances simultaneously. Moreover, if the error is allowed, it becomes much faster. By experiments, we confirm that it achieves about 10 times faster.