Finite-trellis Viterbi decoding returns a maximum-score path

If $T=0$, [F1] gives the unique empty path and its score $1$, which the branch in [F3] returns. If $T\ge 1$, [F2] shows that every positive $D_t(v)$ is attained by a prefix path and a zero value means there is no such prefix. Therefore, for each terminal vertex $v$, $D_T(v)\beta (v)>0$ exactly when some full path ends at $v$; when positive it is the largest score of such a path.

Suppose $T\ge 1$. The finite set of terminal values has a positive maximum exactly when at least one full path exists. If it is positive, let $v_T$ be the maximizing terminal vertex; then $D_T(v_T)>0$ and $\beta (v_T)>0$. If $T=1$, then $D_1(v)=\alpha (v)$ and $Q(v)=\alpha (v)\beta (v)$, so the selected one-vertex tuple $(v_1)$ is already an admissible path of maximum score; no backpointer is needed. If $T\ge 2$, then by [F3], $p_T(v_T)$ is defined and selects an allowed edge from some $v_{T-1}$ with $D_{T-1}(v_{T-1})w_T(v_{T-1},v_T)=D_T(v_T)>0$, so $D_{T-1}(v_{T-1})>0$ because the edge weight is positive. In the $T\ge 2$ case, repeating this argument for the layers $t=T,T-1,\dots ,2$ shows every pointer is defined, each selected pair is an allowed edge, and the chain ends at $v_1$ with $D_1(v_1)=\alpha (v_1)>0$. The chain is therefore a path, and its score is $D_T(v_T)\beta (v_T)$, the maximum terminal value from step 1.1. If all terminal values are zero, step 1.1 shows there is no path, so the algorithm correctly returns “no admissible path.” The $T=0$ case is settled by step 1.1.

The $T=0$ branch takes constant time. For $T\ge 1$, each vertex is initialized or scanned a bounded number of times, each edge contributes one candidate product and comparison, and traceback visits at most $T$ layers. Thus the time is $O(1+T+V+E)$. The algorithm stores at most one backpointer per vertex and scores for the current and preceding layers, so auxiliary storage is $O(1+V)$.