It may seem that all edges entering into deletion states in the Viterbi graph should have weight zero. However, for purposes of the Viterbi graph, deletion states can be thought of as emitting a blank symbol ("-") with probability 1.