Given a received, possibly error-corrupted word, we may associate bit-error probabilities with weights on each edge in the trellis so that the problem of maximum-likelihood decoding reduces to the problem of finding the minimum-weight path from the root to the toor in the trellis. This can be accomplished by a dynamic-programming algorithm known as the Viterbi algorithm  which iteratively finds the most likely prefixes up to depth i.
The Viterbi algorithm requires | E| multiplications and | E| - | V| + 1 additions for the maximum-likelihood decoding of a given vector. By making use of the depth-structure of the trellis, the Viterbi algorithm is able to easily beat even the O(| E| + | V| log| V|) Fibonacci-heap implementation of Dijkstra's algorithm and the DAG-Shortest-Path algorithm for the same task . Moreover, like the Floyd-Warshall algorithm  but faster, the Viterbi algorithm is fairly general and can be applied to any label alphabet with a semiring structure .
Though trellises are found in many common decoding implementations, Lafourcade and Vardy  have shown that their decoding complexity grows exponentially in the length of the code for asymptotically good codes. For this reason, alternative graph structures have been proposed for decoding, such as Tanner graphs  and their generalization to factor graphs .