A Landmark Algorithm for the Time-Dependent Shortest Path Problem

The shortest path problem is one of the most classical problem in combinatorial optimization problem which, given an edge-weighted graph and two vertices, asks to find a path between the two vertices of the minimum length. In this thesis, we consider a generalization of the shortest path problem in which the edge length is time-variable, which we call the time-dependent shortest path problem. This kind of problems has many applications in the fields of navigation systems and others. Since the first algorithm was proposed by Cooke and Halsey in 1966, many studies have been done for this problem. Currently the fastest algorithm is due to Dreyfus and others (1969–1990) who proposed a straightforward generalization of the famous Dijkstra algorithm that is originally developed for the classical shortest path problem. In this thesis, we give an even faster algorithm at a small amount of extra preprocessing cost. The proposed algorithm is based on the ALT algorithm proposed by Goldberg and Harrelson (2005) for the shortest path problem, in which the main idea is to use pre-calculated landmarks in determining the interim distance labels for vertices. Experimental results show our algorithms is several times faster than the generalized Dijkstra algorithm.