1
$\begingroup$

I am able to implement the default uniform cost search (python) to find the shortest path between two nodes (path cost). I followed this pseudocode:

enter image description here

Now, I want to calculate the shortest path with fuel constraint.

Each edge in the graph is associated with a pair of values (𝑋, 𝑌) where 𝑋 denotes the distance and 𝑌 denotes the fuel cost.

enter image description here

The job is to find the shortest path between 𝑆 and 𝑇 such that the accumulated fuel cost along the path does not exceed a fuel budget. Specifically, we want to find the shortest path from S to T not exceeding a fuel budget 11. We can observe that although the path S->2->T has the shortest travel distance 10, its accumulated fuel cost 12 exceeds the fuel budget 11. Thus, this path is infeasible. In this example, the path S->1->T is the shortest feasible path.

What approach should I use for my current UCS algorithm?

Following the original algorithm, it is only adding the neighbor node to the queue if it's not already in the queue, or if the one in the queue has a larger accumulative distance, then I update it with the current shorter accumulative distance. This means at any time, the queue will only have one instance of the node.

Now with this additional fuel cost budget/constraint, what should I modify? Does it seem that now there could be more than one instance of the node with different fuel costs and distance in the queue?

$\endgroup$
9
  • $\begingroup$ What does the "fuel cost" mean and how does it affect the "fuel budget"? I think you'll need to define the problem more carefully. Under what conditions is a path allowable? Must the sum of the fuel costs be at most the fuel budget? Is the fuel cost per unit distance or total for the entire edge? $\endgroup$
    – D.W.
    Feb 17 at 7:11
  • $\begingroup$ @D.W. Thank you for your reply. The fuel cost is the amount of fuel spent to travel between two nodes e.g to get from node A to B, the fuel costs 2. To get from node B to C, the fuel costs 1. Hence to get from A to C, the accumulative fuel cost would be 3 $\endgroup$
    – bawagoc25
    Feb 17 at 12:07
  • $\begingroup$ A shortest path is allowable if the accumulated fuel cost does not exceed the fuel budget. You are right, sum of the fuel costs must be at most the fuel budget. The fuel cost is not per unit distance, it is given for the entire edge $\endgroup$
    – bawagoc25
    Feb 17 at 12:08
  • 1
    $\begingroup$ @InuyashaYagami, I suggest putting that in an answer, rather than in a comment. The Stack Exchange model works better when this kind of thing goes in an answer rather than a comment, as people can upvote it, the question can be treated as answered in a search, etc. $\endgroup$
    – D.W.
    Feb 17 at 16:39
  • 1
    $\begingroup$ If that answer is not satisfactory, I suggest first making sure your question is clear about the problem statement, then leaving a comment on the answer explaining the problem with it and how you know it does not solve the problem. $\endgroup$
    – D.W.
    Feb 18 at 7:57

1 Answer 1

2
$\begingroup$

The problem is known as the constrained shortest path problem. It is known to be $\mathsf{NP}$-hard. The proof is given in the paper: "A dual algorithm for the constrained shortest path problem" (by Gabriel Y. Handler and Israel Zang)

You may want to check this survey for solutions: "A survey of resource-constrained shortest path problems: Exact solution approaches" (by Luigi Di Puglia Pugliese and Francesca Guerriero)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.