Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

250
Visualizações
How can i find the cheapest way in a DAG if i have limited money?

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:

dag

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?

over 4 years ago · Santiago Trujillo
3 Respostas
Responde à pergunta

0

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:

enter image description here

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

over 4 years ago · Santiago Trujillo Relatório

0

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.

over 4 years ago · Santiago Trujillo Relatório

0

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.

over 4 years ago · Santiago Trujillo Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda