  In the $k$-Disjoint Shortest Paths ($k$-DSP) problem, we are given a weighted
graph $G$ on $n$ nodes and $m$ edges with specified source vertices $s_1,
\dots, s_k$, and target vertices $t_1, \dots, t_k$, and are tasked with
determining if $G$ contains vertex-disjoint $(s_i,t_i)$-shortest paths. For any
constant $k$, it is known that $k$-DSP can be solved in polynomial time over
undirected graphs and directed acyclic graphs (DAGs). However, the exact time
complexity of $k$-DSP remains mysterious, with large gaps between the fastest
known algorithms and best conditional lower bounds. In this paper, we obtain
faster algorithms for important cases of $k$-DSP, and present better
conditional lower bounds for $k$-DSP and its variants.
  Previous work solved 2-DSP over weighted undirected graphs in $O(n^7)$ time,
and weighted DAGs in $O(mn)$ time. For the main result of this paper, we
present linear time algorithms for solving 2-DSP on weighted undirected graphs
and DAGs. Our algorithms are algebraic however, and so only solve the detection
rather than search version of 2-DSP.
  For lower bounds, prior work implied that $k$-Clique can be reduced to
$2k$-DSP in DAGs and undirected graphs with $O((kn)^2)$ nodes. We improve this
reduction, by showing how to reduce from $k$-Clique to $k$-DSP in DAGs and
undirected graphs with $O((kn)^2)$ nodes. A variant of $k$-DSP is the
$k$-Disjoint Paths ($k$-DP) problem, where the solution paths no longer need to
be shortest paths. Previous work reduced from $k$-Clique to $p$-DP in DAGs with
$O(kn)$ nodes, for $p= k + k(k-1)/2$. We improve this by showing a reduction
from $k$-Clique to $p$-DP, for $p=k + \lfloor k^2/4\rfloor$. Under the
$k$-Clique Hypothesis from fine-grained complexity, our results establish
better conditional lower bounds for $k$-DSP for all $k\ge 4$, and better
conditional lower bounds for $p$-DP for all $p\le 4031$.
