The multiobjective Dijkstra’s algorithm
Date:
July 08-11, 2018. Co-authored with Sedeño-Noda A. Technical Program, page 68.
Abstract
We address the problem of determining all efficient solutions of the Biobjective Shortest Path (BSP) problem. We generalize Dijkstra’s algorithm to the Multiobjective Shortest Path (MSP) problem since the proposed methods keep only one candidate label per node in a priority queue of size $n$. The algorithm runs in $O(N\log{n} + mNmax2 )$ time and uses $O(N + m)$ space to solve the one-to-all BSP problem determining all non-dominated points in the outcome space and one efficient path associated with each one of them. Here $n$ is the number of nodes, $m$ is the number of arcs, $N$ is the number of non-dominated points in outcome space for the one-to-all BSP problem and $Nmax$ is the greatest number of non-dominated points in the outcome space for the one-to-one s-i BSP problem for all node $i=1,\ldots,n$. For the case of the one-to-one s-t BSP problem, we incorporate the classical Bidirectional Search scheme in the proposed algorithms to reduce the number of iterations in practice. Also, the proposed algorithms include pruning strategies to avoid the computation of unnecessary dominated labels. The result is a fast algorithm to solve the BSP problem in large networks. A computational experiment comparing the performance of the proposed methods and state-of-the-art methods is included.