Viterbi Metric Update

Problem

Perform one add-compare-select update of the Viterbi algorithm. For every next state j, compute new[j] = min over i of metrics[i] + branches[i][j], where branches[i][j] is the branch metric from state i to state j. Return the updated metric list.

Hint

Each next state keeps only the cheapest incoming path.

Test cases

case 1

in: [[0,5],[[0,1],[3,0]]]

expected: [0,1]

case 2

in: [[2,2],[[1,0],[0,1]]]

expected: [2,2]

case 3

in: [[1,4,2],[[0,2,1],[3,0,2],[1,1,1]]]

expected: [1,3,2]

case 4

in: [[0,0],[[5,1],[1,5]]]

expected: [1,1]

Starter codePython

def viterbi_update(metrics, branches):
    # Your code here
    pass

4 test cases · run your code against them in the editor