Faster all-pairs optimal electric car routing

More specifically, for every two vertices $s$ and~$t$ in the graph, the algorithm computes $\alpha_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 negative-cost cycles, optimal paths are not necessarily simple. This improves on a previous $\tilde{O}(mn^{2})$-time algorithm of Dorfman et al. [ESA 2024] for the problem.

The cost of an arc is the amount of charge consumed from 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 negative cost may correspond, for example, to a downhill road segment, while an arc with a positive cost may correspond to an uphill segment. A negative-cost 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 negative-cost cycles. negative-cost 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 $\tilde{O}(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.

Joint work with Haim Kaplan, Mikkel Thorup, Uri Zwick and Robert E. Tarjan. To appear in ICALP 2025.