I have to write an essay about shortest path calculation with Viterbi algorithm. Since I am interested in finding the path with the least weight on the network graph, I am a little bit confused how to model the network since Viterbi works only on trellis graphs. Does Viterbi require directed acyclic graph or it could be used on graph with cycles?

On this link I found some hints how Viterbi is used to compute shortest path. It seems like Bellman Ford algorithm to me, but there is some topological sorting in first step of the algorithm? Why I need it?

  • 1
    $\begingroup$ I only know a Viterbi algorithm for training Markov chains. Which are you referring to? Also, Wikipedia knows only Trellis graphs, which seem immediately suited for your purposes. Please give or reference definitions of the terms you are using! $\endgroup$ – Raphael Feb 3 '16 at 14:14
  • 2
    $\begingroup$ Also, please ask only one question per post. And, what have you tried and where did you get stuck? $\endgroup$ – Raphael Feb 3 '16 at 14:14
  • 2
    $\begingroup$ As far as I understand, Viterbi for shortest path is the same algorithm as Bellman-Ford, on which you can find information on Wikipedia. $\endgroup$ – Yuval Filmus Feb 3 '16 at 14:26
  • 2
    $\begingroup$ @Raphael Welcome to "network theory", which seems to be graph theory, where everything has a different name. $\endgroup$ – David Richerby Feb 3 '16 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.