# Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

This is the same problem here but with one more condition that the sum of the distance cannot be a negative integer.

The full description of the problem is: Is it possible to find a simple path (no repeated vertices) between two vertices in a graph such that the sum of the weights of its constituent edges (the weight of an edge can be negative) is less than K, in which K is a positive number.

I have seen other reductions from the Hamilton Path problem, like

Those questions are different from the one I listed here. How to reduce the Hamilton path problem to this problem? Or is it possible to achieve this?

• I'm confused. Please state the problem you want solved in a self-contained manner, in the question. Do you want to require that the sum of the weights be non-negative, or not? Such a condition doesn't appear in the second paragraph.
– D.W.
Commented Apr 28 at 4:05
• @D.W. Hi, yes I want to require that the sum of the weights be non-negative. In the 2nd paragraph, it is stated as the sum of the weights .... K is a positive number. Commented Apr 30 at 16:18