Consider the problem of finding the best score rather than the item that achieves the best score. Then both of these algorithms are matrix multplications in the tropical semiring. In other words they can be written as matrix multiplications over the reals union $\infty$, where the usual $+$ operation is replaced by $\min$ and multiplication is replaced by $+$. (You may need to think in terms of log probabilities to see the correspondence.)
You can see this by looking at the innermost loops of both algorithms. For example, the viterbi algorithm code at wikipedia has the $\min$ of a bunch of "emit_p[source_state][output] * trans_p[source_state][next_state]" in its innermost loop, just like the $a_{ij}b_{jk}$ in the definition of matrix multiplication. Similarly, if you look at the wikipedia edit distance algorithm the core work is done by a line "d[i, j] := minimum(d[i-1, j] + 1, d[i, j-1] + 1, d[i-1, j-1] + 1)". Again it's the $\min$ of a bunch of sums.
In fact, I wrote one piece of code code to implement both HMM edit distance and Viterbi a while back. Unfortunately that article's probably gobblydegook if you don't know Haskell, but the text around the diagrams may be helpful.
(I should have made clear first time, edit distance and Smith-Waterman are pretty much the same thing, just with different weights.)
