2

Viterbi and Dijkstra's algorithm seem to be used in different contexts:

  • Viterbi algorithm is usually employed to solve maximum likelihood sequence problems (I've used for this purpose in Communications, at least). We usually tackle this kind of problem by using trellis, a special type of graph, to represent the problem.
  • Dijkstra algorithm is used to find the shortest path in informed/weighted path problems. Any type of graph can be employed to represent the problem.

After implementing both algorithms, I felt that they are intrinsically related, but I didn't find references that could build a bridge between them in order to grasp a unified understanding.

How related are Viterbi and Dijkstra's algorithm? Where is the distinct difference between them?

Improve this question
1
  • both algorithms are trying to find some sequence Commented Jun 20, 2024 at 14:01

1 Answer 1

Reset to default
1

Both the Viterbi algorithm and Dijkstra's algorithm are concerned with finding the shortest path through a graph.

The major differences are:

  1. In the Viterbi algorithm, the total cost is a product, not a sum. You could change this into a sum by swapping all the incremental costs for their logarithms.
  2. The Viterbi algorithm visits node in simple BFS order, so no priority queue is required. This works because the trellis is acyclic. You could visit then in Dijkstra order, but that would take longer in the worst case.
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

In the Viterbi algorithm, the total cost is a product, not a sum. - That is not totally true. Product takes place during the likelihood computation of Gaussian processes, but the metrics as summed recursively to find the shortest path.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.