0
$\begingroup$

Is there a textbook/paper that I can reference for the following problem? I am looking for a concise proof that I can cite.

Let $G=(V,E)$ be a weighted directed acyclic graph, and consider $s,t\in V$. Calculate the sum of products of weights along all $s-t$ paths.

The solution is a relatively straightforward dynamic programming algorithm, so I believe there must be some text where the proof is discussed. I tried inspecting the DP chapters of standard algorithms texts (CLRS, Dasgupta), but I can't see anything similar.

Improve this question
$\endgroup$
3
  • $\begingroup$ The DP chapter of CLRS comes before they've introduced graphs. You might have better luck looking through the exercises in the chapter on graph algorithms. $\endgroup$
    – Peter Taylor
    Commented Sep 30, 2022 at 12:14
  • $\begingroup$ This is a standard problem in the core of Hidden Markov Models. A nice exposition is given in Chapter 10 of Bioinformatics Algorithms textbook. $\endgroup$
    – Max Alekseyev
    Commented Sep 30, 2022 at 12:19
  • $\begingroup$ Also, Chapter 10 material is nicely presented in these video lectures. The algorithm in question is explained at the end of "The Viterbi Algorithm" part. $\endgroup$
    – Max Alekseyev
    Commented Sep 30, 2022 at 16:50

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .