By Lemma 3.2, computing minimum-cost plans in the original graph would then reduce to finding shortest paths in G0,B with respect to the cost function B. More specifically, B(s, t) = B (s 0 , t0 ), for every s, t V , where B (s 0 , t0 ) is the distance from s 0 to t 0 with respect to B. (Note that t 0 here stands for reaching t with a charge of at least 0. When there are negative arc costs, a minimum-cost plan may reach the destination with strictly positive charge.) We next describe how the new costs B(u a , vb ) are computed. This is the main step of our reduction. Consider the cheapest way of getting from u a to v b , i.e., from u with initial charge a to v with final charge at least b, with (an optional) recharging at a given vertex x V along the way. Recharging is not allowed in any other vertex. (We do not assume that u, v and x are distinct. We may even ha

) Clearly, we should choose a path from u a to x that reaches x with the maximum possible charge, namely B,a(u, x). We then buy just enough charge at x to reach v with a charge of at least b. The minimum initial charge at x required to reach v b is B,b(x, v). The amount of charge we need to buy at x is thus (B,b(x, v) B,a(u, x))+, where z + = max{0, z}. (If B,a(u, x) > B,b(x, v), we do not need to recharge at x.) Considering all choices for the recharging vertex x, including u and v, we get: (u a , vb ) = min xV r(x) (B,b(x, v) B,a(u, x))+ . We allow the case x = u, in which case B,a(u, u) a. (Strict inequality is possible in the presence of negative cycles.) We also allow the case x = v, in which case B,b(v, v) b. (Again a strict inequality is possible in the presence of negative cycles.) To compute (u a , vb ) we first remove the + from the definition of (u a , vb ), namely, (u a , vb ) = min xV r(x) (B,b(x, v) B,a(u, x)) . It is then easy to see that (u a , vb

) = (u a , vb ) + , as if (u a , vb ) < 0 then it is possible to get from u a to v b without recharging, i.e., at cost 0. To compute (u a , vb ) we form a layered graph (V 0,B U) (U V 0,B), where U = {x V | r(x) < }. (We assume that different copies of V 0,B are used in the first and third layers of this graph, see Figure 2.) We let w(u a , x) = r(x)B,a(u, x) , w(x, vb ) = r(x)B,b(x, v) . Now (u a , vb ) can be computed using a single min-plus product.2 The time required is O(n 3 ) using the nave algorithm, or slightly faster using the algorithm of Williams [13, 14], assuming that all B,a(u, x) and B,b(x, v) values are given to us. The following lemma formally proves the correctness of the reduction. Recall that B (s 0 , t0 ) is the distance from s 0 to t 0 in the graph G0,B with respect to B. Lemma 3.3. B(s, t) = B (s 0 , t0 ), for every s, t V . Proof. Any path P from s 0 to t 0 in the complete graph G0,B with the cost function B corresponds to a plan P from s to t in t

More specifically, let P be the path s = y 0 0 , y a1 1 , . . . , y ak1 k1 , y0 k = t. Then each arc (y ai i , y ai+1 i+1 ) can be replaced by a plan in the original graph G whose cost is (y ai i , y ai+1 i+1 ). Concatenating all these plans we get a plan P in G whose total cost is B(P) = Pk1 i=0 (y ai i , y ai+1 i+1 ). Thus, B(s, t) B (s 0 , t0 ). Conversely, let P be a minimum-cost plan from s to t in the original graph G. By Lemma 3.2 there are states y