# Finding an exactly weighted st-path in a digraph [closed]

I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic.

The question is: given 2 nodes $v_1$ and $v_2$, is there a path from $v_1$ to $v_2$ with a weight $w$.

I would like to know if there are any known complexity results for this problem, or even anything related to this but with a specific weight, and not just shortest path, longest path etc. I have been thinking of representing the problem as in-equations in some type of linear programming, but before I start I'd like to get as much info as possible :)

• This is not a research-level question, there are standard algorithms for this problem that can be found in most algorithm textbooks. Thus the question is off-topic here. Try asking on cs.stackexchange.com instead. – Jan Johannsen Sep 18 '14 at 14:34
• There is a simple reduction from directed stHamPath. – Kaveh Sep 18 '14 at 16:08
• Crossposted on CS.SE – Juho Sep 19 '14 at 7:32

Given numbers $\{x_1,\ldots,x_n\}$ and a target number $T$, construct the complete transitive acyclic graph $G=(\{x_1,\ldots,x_n\}\cup \{v_1,v_2\}, E)$,
Where $E=\{(v_1,x_i)|i\in [n]\}\cup \{(x_i,v_2)|i\in [n]\}\cup \{(x_i,x_j)|1\leq i<j\leq n\}$, and $w(x_i,v_2)=0$, $w(v_1,x_j)=w(x_i,x_j)=x_j$.
Now simply ask if there exists a $v_1\leadsto v_2$ path of weight $T$.