Consider an acylicic directed weighted graph in which the nodes represent cities and the weights represent the amount of fuel a car spends when going through that edge. At each city $u$ the car refuels an amount equal to $F(u)$ of fuel. The car cannot traverse an edge if it doesn't have enough fuel to do so. Consider that the car has to travel from city $s$ to city $t$, and starts his travel with an amount equal to $F_0$ of fuel. Find the path in which the car reaches $t$ with the most amount of fuel left.

For solving this problem I created a copy $G'$ of the original graph. Starting from node $s$ I traverse the whole graph and remove the edges in which it is not possible for the car to traverse the edge because it would run out of fuel. Then, I create a copy $G''$ of $G'$ in which its edges are the original weight plus the amount of fuel the car charges when getting to the ending node of the edge. Finally, running the Bellman-Ford or Dijkstra's algorithm on $G''$ but with the weights multiplied by $-1$ would get me the answer. Is this answer correct of is there a more efficient way?

  • $\begingroup$ Don't run Dijkstra, it doesn't deal well with negative edges $\endgroup$
    – nir shahar
    Oct 12 at 5:32
  • 2
    $\begingroup$ A previous question can be seen as the same as this question. Please see my hint for a more efficient way over there. $\endgroup$
    – John L.
    Oct 13 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.