Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions

Keerti Choudhary, Amit Kumar, Lakshay Saggi

We study the 2-Disjoint Shortest Paths (2-DSP) problem: given a directed weighted graph and two terminal pairs $(s_1,t_1)$ and $(s_2,t_2)$, decide whether there exist vertex-disjoi…