  We study a constrained shortest path problem in group-labeled graphs with
nonnegative edge length, called the shortest non-zero path problem. Depending
on the group in question, this problem includes two types of tractable variants
in undirected graphs: one is the parity-constrained shortest path/cycle
problem, and the other is computing a shortest noncontractible cycle in
surface-embedded graphs.
  For the shortest non-zero path problem with respect to finite abelian groups,
Kobayashi and Toyooka (2017) proposed a randomized, pseudopolynomial-time
algorithm via permanent computation. For a slightly more general class of
groups, Yamaguchi (2016) showed a reduction of the problem to the weighted
linear matroid parity problem. In particular, some cases are solved in strongly
polynomial time via the reduction with the aid of a deterministic,
polynomial-time algorithm for the weighted linear matroid parity problem
developed by Iwata and Kobayashi (2021), which generalizes a well-known fact
that the parity-constrained shortest path problem is solved via weighted
matching.
  In this paper, as the first general solution independent of the group, we
present a rather simple, deterministic, and strongly polynomial-time algorithm
for the shortest non-zero path problem. The algorithm is based on Dijkstra's
algorithm for the unconstrained shortest path problem and Edmonds' blossom
shrinking technique in matching algorithms; this approach is inspired by
Derigs' faster algorithm (1985) for the parity-constrained shortest path
problem via a reduction to weighted matching. Furthermore, we improve our
algorithm so that it does not require explicit blossom shrinking, and make the
computational time match Derigs' one. In the speeding-up step, a dual linear
programming formulation of the equivalent problem based on potential
maximization for the unconstrained shortest path problem plays a key role.
