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:
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.
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?