[EDIT]This is now a complete answer
A counter exemple for your solution is:
$v_1 \xrightarrow{2} v_2$ ;
$v_1 \xrightarrow{1} v_3$ ;
$v_2 \xrightarrow{0} v_3$ ;
$v_2 \xrightarrow{1} v_4$ ;
$v_3 \xrightarrow{2} v_4$ .
The first maximal path will give you this path $v_1\xrightarrow{2} v_2 \xrightarrow{0} v_3\xrightarrow{2} v_4$ of weight 4. And the second maximal has weight 1 (hence for a total of 5). But you can get a better total by taking $v_1 \xrightarrow{2} v_2 \xrightarrow{1} v_4$ and $v_1 \xrightarrow{1} v_3 \xrightarrow{2} v_4$ for a total of 6.
A solution
Let $G=(V,E,w)$ be a DAG.
Let $m=m_1...m_n$ be a path of maximum in $G$.
We define $G_m=(V',E',w')$ as follow:
- $V'=\{m_1,...,m_n\}\times V$
- $E'=\{((m_i,v),(m_i,v'))\mid (v,v')\in E\}\cup \{((m_i,m_j),(m_j,m_k))\mid i<k<j\}$
- $w'((m_i,v),(m_i,v'))=w(v,v')$ if $(v,v')$ do no belong to the maximal path, $0$ otherwise
- $w'((m_i,m_j),(m_j,m_k))=-w(m_k...m_j)$
Let $m'$ be the maximal path in $G_m$, the maximal sum you are looking for is equal to $w(m)+w'(m')$!
You can compute it in polynomial time since finding a maximal path is linear in DAGs and the second DAG has a size polynomial in the first.
I let you the joy of proving this solution correct ...
The intuition behind it is:
- I find the maximal path in $G$
- But it may be the case that I made a wrong choice maximizing the first path without caring about the second
- So I allow the second path to correct the first by going up the first path (taking negative reward). This is done when there is a change of copies (going from $m_i\times V$ to $m_j\times V$
- I can correct only once each edge of the graph (this is the reason of the inequality $i<k<j$).
Please ask if something is not clear or if I made a mistake. I didn't do the full proof. But I hope it is correct.
Edit 2: on an exemple
Considere the graph given as a counter example for your solution.
The maximal path is : $m=v_1 \to v_2 \to v_3 \to v_4$. thats gives 4.
$G_m$ is has follow : for $k\in\{1,2,3,4\}$ :
$(v_k,v_1) \xrightarrow{0} (v_k,v_2)$ ;
$(v_k,v_1) \xrightarrow{1} (v_k,v_3)$ ;
$(v_k,v_2) \xrightarrow{0} (v_k,v_3)$ ;
$(v_k,v_2) \xrightarrow{1} (v_k,v_4)$ ;
$(v_k,v_3) \xrightarrow{0} (v_k,v_4)$ ;
$(v_1,v_3)\xrightarrow{-0}(v_3,v_2)$ ;
$(v_1,v_4)\xrightarrow{-(0+2)}(v_4,v_2)$ ;
$(v_1,v_4)\xrightarrow{-2}(v_4,v_3)$ ;
.
The maximal path is $(v_1,v_1)\xrightarrow{1} (v_1,v_3)\xrightarrow{-0}(v_3,v_2)\xrightarrow{1}(v_3,v_4)$ that gives you 2.
Thus the solution is 6.
Notice that here the second maximal path somehow "correct" the first maximal path by taking $(v_1,v_3)\xrightarrow{-0}(v_3,v_2)$.
The graph you describe is in fact a Markov chain. What you are looking for is the expected value of the path for $St$ to $E1$. Notice that there is no notion of maximum value, since there are no choice to make, all the choices are made by the probability on the edges
In Markov chain, you can actually compute this value as the solution of the following equations:
Let $Trap(E1)$ be the set of nodes from which $E1$ is not accessible
For any node $n$ define the variable $x_n$ that represent the expect value of the path from $n$ to $E_1$.
If $n\in Trap(E)$ then add the equation $x_n=0$.
More over $x_{E1}=0$
For all node $n\in N\setminus Trap(E1)$ add the equation:
$$ x_n = \sum_{n'\in N\setminus Trap(E1)} p(n,n')(w(n,n')+x_{n'})$$
where $p(n,n')$ denotes the probability to take an edge form $n$ to $n'$ and $w(n,n')$ the weight of this edge.
You have $|N|$ variables and $|N|$ equations thus an unique solution.
the value you are looking for is $x_{St}$
On your example it gives:
$$x_{St}=0.8(1+x_{z_1})+0.2(x_{z_3}+1)$$
$$x_{z_3}=0.6(1+x_{z_2})$$
$$x_{z_2}=0.1(3+x_{St})+0.5(x_{z_4}+3)+0.1(x_{E1}+3)$$
$$x_{Z_1}=0.75(1+x_{z_2})+0.5(x_{z_4}+1)$$
$$x_{z_4}=4+x_{E_1}$$
And I let you solve it by elimination of variables for example.
Best Answer
If the vertices are already in topological order (that is, all edges go from left to right) then you can start at $s$ and go in order. For each vertex, compute the maximum cost path from $s$ to that vertex, by considering all the edges that point into that vertex.
This takes $O(|V|+|E|)$ time.
If the vertices are not already sorted this way, then you should look at one of these algorithms for fixing that. These also take $O(|V|+|E|)$ time.
In general, this is nearly always the setup for dynamic programming in a directed acyclic graph, just because the topological sort is the primary way we can take advantage of the lack of cycles.