A variation on the Dijkstra shortest path algorithm

Question

I'm stuck on this problem (my solution is too slow). I'll describe the problem then my solution.

Problem: Given N stations, each at a position x_i on the number line, we want to move a robot from the first station to the last station (stations are sorted in non-decreasing x_i order) at the lowest monetary cost. We have a robot that starts out with a maximally charged battery with K (not necessarily integral) units of power, and can move E (not necessarily integral) units of length per unit of power spent. At any station in-between the first and last station we can recharge. Each station charges the same flat rate F dollars to start charging, plus c_i dollars per unit power replenished. The robot ONLY can charge if its power at the time is at or below K/2 OR it cannot reach the next station without charging; every time the robot charges, it has to charge to 100% (i.e. K).

My solution: I'm pretty sure this is a variation on a shortest path problem, except we are optimizing for monetary cost. I'm running Dijkstra SSSP. However, for each state we need to keep track of both monetary cost and energy remaining, because racking up a higher cost earlier on by charging at a cheap station may be better than saving your money until the end. So instead of keeping maintaining cost[i]=cheapest known way to get to station i, I maintain cost[i][energy]=cheapest known way to get to station i with a certain energy. In the priority queue, I order the states by cost only because I'm not sure there's a way to create a heuristic for both cost and energy remaining. This algorithm is really slow on some test cases because if E and K were large, then each station can potentially travel to every station in front of it, creating a massive graph. I think I have to prune the search frontier, but I'm not sure how. Any ideas?

Answer 1

This sounds more like a job for dynamic programming than Dijkstra's. The optimal cost from a station i is irrespective of the choices you made before arriving there.

Move backwards through the stations. For station i, consider all stations j > i that you can reach from there (you already computed their optimal cost). Choose the optimum among these.

In pseudocode:

opt[N-1] = 0                                        // cost of the last station is 0
for i = N-2 down to 0                               // loop backwards over the stations
    opt[i] = infinity
    for j = i+1 to N-1 where (x_j - x_i) * E <= K   // loop over all next stations that can be reached without a flat battery
        energyToJ = (x_j - x_i) * E
        if (energyToJ >= K/2                        // we are allowed to recharge
          or j == N-1                               //  or we cannot reach the next station because there is none
          or x_{j+1} - x_i) * E > K)                //   or because it is too far
            costJ = F + energyToJ * c_j + opt[j]    // total cost via j is cost to j + cost from j
            if (costJ < opt[i])                     // keep track of the optimal cost
                opt[i] = costJ                      

return opt[0]

---

edit

Since dynamic programming is not an option for you, this is how I would approach it using Dijkstra's:

From a station i you can move directly to each station j for which one of the following holds:

• K/2 <= x_j - x_i <= K
• 0 <= x_j - x_i < K/2 and there is no j' > j for which x_j' - x_i <= K

Create a graph with N vertices, one for each station. There is a directed edge e_ij from station i to station j, if and only if one of the two conditions above holds. The weight of e_ij is simply the cost of recharging there, which is F + (x_j - x_i) * c_j.

You can now just run Dijkstra's on this graph to find the most economical way to get to the final station. The reason we don't need to keep track of both distance and money is that the distance is already encoded in the structure of the graph: the edges of the graph are exactly all possible moves from one station to another.