How can i find the cheapest way in a DAG if i have limited money?

Question

So, if i have an Directed Acyclic Graph where the cost of each edge either 0 or more than 0, if its more than 0 it will have a negative-weight (So you can by it for 5$ and it will shorten your way by -20 for example).

I know that we can easily find a shortest/cheapest way in a DAG, but what if we have limited money?

So imagine the next situation:

We have 8 money.The algorithm would find the shortest path which is -10+-3= -13, but it would cost 12 but we only have 8 money, so its not an option. The ideal path would be -10+0 which only costs 7 money. Is there an algorithm which i can use to solve this problem?

Answer 1

This problem is NP-Hard, with a reduction from Knapsack-Problem.

Short intuitive "proof": The idea is, create a vertex for each item - you can either "take it" or "not take it" by choosing the vertex with the cost or the "free" vertex.

Sketch:

In the above you can see, from the Knapsack Problem, create a graph, for each item, you can choose to take it - and pay the cost and gain the "value", or ignore it.

More formally:

Given an instance of knapsack with weights=w1,w2,w3,...cn and cost=c1,c2,..,cn, with some maximal weight W, create a graph G=(V,E) with

V= { V_i,U_i,W_i | i=0,...n }
E= { (W_i,V_i+1,U_i+1 | i=0,...,n-1} U {(V_i,W_i+1), (U_i,W_i+1) | i=0,...,n-1 }

value(W_i,V_i+1) = c_i+1
money(W_i,V_i+1) = w_i+1
value(W_i,U_i+1) = 0
money(W_i,U_i+1) = 0
money(V_i,W_i+1) = cost(V_i,W_i+1) = money(U_i,W_i+1) = cost(U_i,W_i+1) = 0

The solution to this problem that uses at most W money, will be also the solution for knapsack with maximal capacity of W.

---

A possible pseudo polynomial solution could be (using Dynamic Programming technique):

D(start,0) = 0
D(v,x) = infinity     x < 0
D(v,x) = min { D(u,x-money(u,v)) + value(u,v) | for each edge (u,v) } U {infinity}

In the above D(v,x) is the minimal distance needed to travel from the start node to v, paying exactly x money.

Note that it can be done because it's a DAG, so you can calculate the values from first to last according to the graph's topological sort.

When done, you need to search all values of x from 0 to MAXIMAL_AMOUNT_OF_MONEY_ALLOWED to find the minimal value of D(target,x), and that's the answer.
Finding the actual cost is done by retracing back your steps, as done in other Dynamic Programming solutions.

The above run time is O(|V|*MAX_MONEY + |E|)

Answer 2

Use flood algorithm. Rules:
In each visited node update an array of paths and their prices.
Release the array when the visited node is no more needed.
Always remove paths with price > money.
Start flood in the source node.
End flood in the target node when all incoming edges are flooded.
Follow flood using outgoing edges when all incoming edges are flooded.
At the end take the path with highest price in the target node.

Answer 3

Since your question is not about path-finding in general and only about finding a path within a certain cost, I will assume you have some algorithm for finding the shortest path already and will speak in general about how to modify it.

The simplest way would be to just ignore the paths which increase the cost beyond the amount you want to spend. In your path-finding algorithm, when you are adding an edge to a path, abandon that path if the sum cost is now too high. If it is reasonable to just skip it or mark it invalid some way in your code, do it, otherwise you could treat the sum weight for the path as infinity, then it will handle itself.

Assuming you have some function for checking the next edge along the path (and if you don't, or not in this format, then just adapt it to what you do have)...

// accepts the edge you are checking, max cost, and the sum weight and cost so far to this point
// returns float array {sum cost, sum weight), or infinity if cost is exceeded
void checkNextStep(Edge* edge, float maxCost, float* sumWeight, float* sumCost)
{
    if(*sumCost + edge->cost > maxCost)
    {
        *sumWeight = INFINITY;
        *sumCost += edge->cost;
    }
    *sumWeight += edge->weight;
    *sumCost += edge->cost;
}

Now that path will automatically be rejected if the cost goes above your threshold, because infinity will likely not be the shortest path.

If you end up getting a shortest path with weight infinity, then that means you do not have enough money to get to your target node at all, by any path. So you can use that as a check that you can't get there at all with your money system.