# 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 :)

## closed as off-topic by Kaveh, Hsien-Chih Chang 張顯之, David Eppstein, Lev Reyzin♦Sep 19 '14 at 14:20

This question appears to be off-topic. The users who voted to close gave these specific reasons:

• "Our site policy prohibits simultaneous crossposting: it duplicates effort and fractures discussion. Crossposting is permitted after a week has passed without a satisfying answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link between the copies in both directions." – Lev Reyzin
• "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, Hsien-Chih Chang 張顯之, David Eppstein
If this question can be reworded to fit the rules in the help center, please edit the question.

• 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$.