Polynomial Time Prioritized Multi-Criteria $k$-Shortest Paths and $k$-Disjoint All-Criteria-Shortest Paths

The Shortest Path Problem, in real-life applications, has to deal with multiple criteria. Finding all Pareto-optimal solutions for the multi-criteria single-source single-destination shortest path problem with non-negative edge lengths might yield a solution with the exponential number of paths. In the first part of this paper, we study specific settings of the multi-criteria shortest path problem, which are based on prioritized multi-criteria and on $k$-shortest paths. In the second part, we show a polynomial-time algorithm that, given an undirected graph $G$ and a pair of vertices $(s,t)$, finds prioritized multi-criteria 2-disjoint (vertex/edge) shortest paths between $s$ and $t$. In the third part of the paper, we introduce the $k$-disjoint all-criteria-shortest paths problem, which is solved in time $O(min(k|E|, |E|^{3/2}))$.