Leírás
We study the problem of finding a shortest non-zero path in group-labeled graphs with nonnegative edge length. For the problem with respect to finite abelian groups, Kobayashi and Toyooka (2017) proposed a randomized, pseudopolynomial algorithm via permanent computation. For a slightly more general class of groups, Yamaguchi (2016) reduced the problem to the weighted linear matroid parity problem. In particular, some cases are solved in strongly polynomial time with the aid of a deterministic, polynomial algorithm for the weighted linear matroid parity problem developed by Iwata and Kobayashi (2017), which generalizes a well-known fact that the shortest odd/even path problem in undirected graphs is solved via weighted matching. In this talk, as the first general solution independent of the group, we present a rather simple, deterministic, and strongly polynomial algorithm for the shortest non-zero path problem. The algorithm is based on Dijkstra's algorithm and Edmonds' blossom shrinking technique in matching algorithms.