  We present a novel algorithm that solves the turbo code LP decoding problem
in a fininte number of steps by Euclidean distance minimizations, which in turn
rely on repeated shortest path computations in the trellis graph representing
the turbo code. Previous attempts to exploit the combinatorial graph structure
only led to algorithms which are either of heuristic nature or do not guarantee
finite convergence. A numerical study shows that our algorithm clearly beats
the running time, up to a factor of 100, of generic commercial LP solvers for
medium-sized codes, especially for high SNR values.
