  The well-known $k$-disjoint path problem ($k$-DPP) asks for pairwise
vertex-disjoint paths between $k$ specified pairs of vertices $(s_i, t_i)$ in a
given graph, if they exist. The decision version of the shortest $k$-DPP asks
for the length of the shortest (in terms of total length) such paths. Similarly
the search and counting versions ask for one such and the number of such
shortest set of paths, respectively.
  We restrict attention to the shortest $k$-DPP instances on undirected planar
graphs where all sources and sinks lie on a single face or on a pair of faces.
We provide efficient sequential and parallel algorithms for the search versions
of the problem answering one of the main open questions raised by Colin de
Verdiere and Schrijver for the general one-face problem. We do so by providing
a randomised $NC^2$ algorithm along with an $O(n^{\omega})$ time randomised
sequential algorithm. We also obtain deterministic algorithms with similar
resource bounds for the counting and search versions.
  In contrast, previously, only the sequential complexity of decision and
search versions of the "well-ordered" case has been studied. For the one-face
case, sequential versions of our routines have better running times for
constantly many terminals. In addition, the earlier best known sequential
algorithms (e.g. Borradaile et al.) were randomised while ours are also
deterministic.
  The algorithms are based on a bijection between a shortest $k$-tuple of
disjoint paths in the given graph and cycle covers in a related digraph. This
allows us to non-trivially modify established techniques relating counting
cycle covers to the determinant. We further need to do a controlled
inclusion-exclusion to produce a polynomial sum of determinants such that all
"bad" cycle covers cancel out in the sum allowing us to count "good" cycle
covers.
