The output of the Viterbi algorithm is literally the single highest probability path, not a random sample from the posterior distribution of the state trajectories. To get a random sample of a trajectory, instead use the forward-backward algorithm, but instead of smoothing during the backward pass to compute the marginal probabilities associated with the states, actually sample during the backward pass to get a sample from the joint distribution of the states.
Here’s an example for use in dynamic occupancy models. Contrast this forward-filtering-backward-sampling function with the previous forward-filtering-backward-smoothing function, which is what is most commonly meant when we say “forward-backward algorithm”.
https://github.com/jsocolar/flocker/blob/main/R/get_Z.R/#L500