A biobjective Dijkstra algorithm

Abstract

We generalize the Dijkstra algorithm to the Biobjective Shortest Path (BSP) problem. The proposed method keeps only one candidate label per node in a priority queue of size n. In this way, we introduce a novel algorithm to solve the one-to-all BSP problem determining all non-dominated points in the outcome space and one efficient path associated with each of them. For the case of the one-to-one BSP problem, we incorporate the classical bidirectional search scheme in the proposed algorithm to reduce the number of iterations in practice. The proposed algorithm also includes pruning strategies to avoid the computation of unnecessary labels. The result is a fast algorithm to solve the one-to-one BSP problem in large networks. A computational experiment comparing the performance of the proposed method and the state-of-the-art methods is included.