This is the 18th day of my participation in the August Challenge

Viterbi algorithm is a special but most widely used dynamic programming algorithm, using dynamic programming, can solve the shortest path problem in any graph. Viterbi algorithm is proposed to solve the shortest path problem of a Lattice of fence network. It is important because it can be used to decode all kinds of problems described by hidden Markov models, including today’s digital communication, speech recognition, machine translation, conversion of pinyin to Chinese characters, word segmentation and so on

The feature of the directed graph of the fence network is that there are multiple nodes in the same column and they are interlaced with the nodes in the previous column. The same column node represents the arrangement of different states at the same point in time. To put it bluntly, it’s like a neural network

Find the shortest path from S to E, as shown in the figure below

First, we assume that there is a shortest path (red) from S to E, and that this path passes through C2, then we must be certain that of the 64 (4X4X4=64) subpaths from S to C2, this subpath must be the shortest. Proof: proof by contradiction. If there is a shorter subpath between S and C2, it can be used instead of the original path, which is obviously not the shortest, contradicting the null hypothesis.)

Similarly, we can also conclude that the shortest subpath between two points is from S to B2. ** In this case, if we calculate the shortest path from S to C2, do we just consider the shortest path from S to all nodes of layer B? ** The answer is yes! Because the “global shortest” path from S to E must pass through these “locally shortest” subpaths.

The formula is given below. F (I)f(I)f(I) is the value of the shortest path from SSS to node III, dist(I,j)\text{dist}(I,j)dist(I,j) is the distance from node III to node JJJ. the


f ( E ) = min ⁡ ( f ( i ) + dist ( i . E ) ) .     i = A 1 . A 2 . . . . . C 4 f(E)=\min(f(i)+\text{dist}(i,E)),\ \ \ i=A_1,A_2,… ,C_4

The pseudocode is as follows:

f[1] =0
pre[1] = 0 # pre[I]=j indicates the shortest path from j to I
for i in range(point_num): # walk through all the points
    for j in incominglist: # Walk through all paths to this point
        best_score = inf
        score = f[j] + dist(j, i)
        if score < best_score:
            best_score = score
            pre[i] = j
Copy the code