# Longest path in a directed acyclic graph with constraints

Given a directed weighted acyclic graph G=(V,D,W) and a subset of edges D' of D. The problem is to find the longest path in G that passes by exactly one edge of D'.

What is the complexity of this problem?

You can solve this problem in time $$O(|V|+|E|)$$ by using dynamic programming. Thirst you order nodes in topological order. Let $$v_i$$ be the $$i$$-th node in topological order. Let $$E_i$$ be the set of edges ending in $$v_i$$.
If $$|E_i\setminus D'| = 0$$ then: $$d[v_i][0] = 0$$
otherwise: $$d[v_i][0] = 1 + \max_{(v_j, v_i) \in E_i}(d[v_j][0]_{(v_j, v_i) \not\in D'})\\$$
If $$|E_i| = 0$$ then: $$d[v_i][1] = -\infty$$ otherwise: $$d[v_i][1] = 1 + \max_{(v_j, v_i) \in E_i}(d[v_j][0]_{(v_j, v_i) \in D'}, d[v_j][1]_{(v_j, v_i) \not\in D'})$$
It's easy to see that $$d[v_i][0]$$ is equal to length of longest path ending in $$v_i$$ without edges from $$D'$$ and $$d[v_i][1]$$ is equal to length of longest path ending in $$v_i$$ with exactly one edge from from $$D'$$. After that you need to find largest of $$d[v_i][1]$$. You can also store the id of the node for which we found the maximal value during dynamic programming to recreate the path.