Faster All-Pairs Optimal Electric Car Routing

We present a randomized Õ(n^3.5)-time algorithm for computing optimal energetic paths for an electric car between all pairs of vertices in an n-vertex directed graph with positive and negative costs, or gains, which are defined to be the negatives of the costs. The optimal energetic paths are finite and well-defined even if the graph contains negative-cost, or equivalently, positive-gain, cycles. This makes the problem much more challenging than standard shortest paths problems. More specifically, for every two vertices s and t in the graph, the algorithm computes αB(s,t), the maximum amount of charge the car can reach t with, if it starts at s with full battery, i.e., with charge B, where B is the capacity of the battery. The algorithm also outputs a concise description of the optimal energetic paths that achieve these values. In the presence of positive-gain cycles, optimal paths are not necessarily simple. For dense graphs, our new Õ(n^3.5) time algorithm improves on a previous Õ(mn²)-time algorithm of Dorfman et al. [ESA 2023] for the problem. The gain of an arc is the amount of charge added to the battery of the car when traversing the arc. The charge in the battery can never exceed the capacity B of the battery and can never be negative. An arc of positive gain may correspond, for example, to a downhill road segment, while an arc with a negative gain may correspond to an uphill segment. A positive-gain cycle, if one exists, can be used in certain cases to charge the battery to its capacity. This makes the problem more interesting and more challenging. As mentioned, optimal energetic paths are well-defined even in the presence of positive-gain cycles. Positive-gain cycles may arise when certain road segments have magnetic charging strips, or when the electric car has solar panels. Combined with a result of Dorfman et al. [SOSA 2024], this also provides a randomized Õ(n^3.5)time algorithm for computing minimum-cost paths between all pairs of vertices in an n-vertex graph when the battery can be externally recharged, at varying costs, at intermediate vertices.