Finding the shortest path in a graph without any negative prefixes

Question

Find the shortest path from source to destination in a directed graph with positive and negative edges, such that at no point in the path the sum of edges coming before it is negative. If no such path exists report that too.

I tried to use modified Bellman Ford, but could not find the correct solution.

---

I would like to clarify a few points :

1. yes there can be negative weight cycles.
2. n is the number of edges.
3. Assume that a O(n) length path exists if the problem has a solution.
4. +1/-1 edge weights.

Answer 1

Admittedly this isn't a constructive answer, however it's too long to post in a comment...

It seems to me that this problem contains the binary as well as discrete knapsack problems, so its worst-case-running-time is at best pseudo-polynomial. Consider a graph that is connected and weighted as follows:

Then the equivalent binary knapsack problem is trying to choose weights from the set {a₀, ..., a_n} that maximizes Σ a_i where Σ a_i < X.

As a side note, if we introduce weighted loops it's easy to construct the unbounded knapsack problem instead.

Therefore, any practical algorithm you might choose has a running time that depends on what you consider the "average" case. Is there a restriction to the problem that I've either not considered or not had at my disposal? You seem rather sure it's an O(n³) problem. (Although what's n in this case?)