Faster All-Pairs Optimal Electric Car Routing
Abstract
We present a randomized -time algorithm for computing optimal energetic paths for an electric car between all pairs of vertices in an -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 and in the graph, the algorithm computes , the maximum amount of charge the car can reach with, if it starts at with full battery, i.e., with charge , where 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 time algorithm improves on a previous -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 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 -time algorithm for computing minimum-cost paths between all pairs of vertices in an -vertex graph when the battery can be externally recharged, at varying costs, at intermediate vertices.
Keywords and phrases:
EV routing, Shortest Paths, Shortcuts, SamplingCategory:
Track A: Algorithms, Complexity and GamesFunding:
Dani Dorfman: Partially supported by grant 2854/20 of the Israeli Science Foundation.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Shortest pathsAcknowledgements:
This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing.Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
Let be a weighted directed graph, where is the set of vertices, is the set of arcs, and where is a real-valued cost function defined on the arcs. The cost of an arc 111For brevity we denote an arc from to by , rather than . is the amount of energy consumed when traversing the arc. Throughout most of this paper, it is more convenient to work with a gain function rather than a cost function. The gain of an arc is simply , i.e., the amount of energy gained by traversing the arc. The gain is negative if moving from to requires spending energy, or positive if energy is gained by moving from to .
A weighted directed graph , where is a gain function, may be viewed as modeling a road network on which an electric car can roam. The electric car is assumed to have a battery of capacity , where is a parameter, i.e., it can store up to units of energy. The charge, i.e., the amount of energy in the battery, can never be negative, and can never exceed the capacity of the battery. If the car is currently at vertex with charge in its battery, where , then it can traverse an arc if and only if . If this condition holds, and the car traverses the arc, then it reaches with a charge of . The car can traverse if , but the battery does not charge beyond its capacity of . The car can traverse a path if and only if it can sequentially traverse its arcs. Throughout most of the paper we assume that no external charging of the battery is allowed. The battery is only charged by traversing arcs with positive gain. We may assume that , for every , as arcs with can never be used, and can thus be removed, and gains can be changed to without changing the problem. We consider the following two related natural questions:
-
1.
Given two vertices , what is the maximum final charge, denoted , with which the car can reach if it starts at with full battery, i.e., with a charge of ? If the car cannot reach even with an initial charge of at , we let . More generally, we let , where , be the maximum final charge with which the car can reach if it starts at with a charge of .
-
2.
Given two vertices , what is the minimum initial charge at , denoted , that enables the car to reach ? If the car cannot reach even with an initial charge of at , we let . More generally, we let , where , be the minimum initial charge at required for reaching with a charge of at least .
It is not difficult to see, as shown in Dorfman et al. [5, Corollary 5.2], that , where denotes the maximum final charge at when starting at with full battery in the reverse of the graph. Thus, the problems of computing maximal final charges and minimum initial charges are computationally equivalent. (Note, however, that due to the reverse operation used, the single-source version of the maximum final charge problem becomes equivalent to the single-target version of the minimum initial charge problem.) In this paper, we only work with maximal final charges.
If all arc costs are nonnegative, i.e., all gains are nonpositive, then it is easy to see that , and , if , where is the standard distance from to with respect to the costs of the arcs. Otherwise, and . When costs and gains can be both positive and negatives, the problem becomes more complicated. If there are no positive-gain cycles in the graph, the problem can be solved using fairly simple adaptations of standard shortest paths algorithms. Thus, the single-source version of the maximal final charges problem can be solved in time using an adaptation of the classical Bellman-Ford algorithm [2, 7], and the all-pairs version of the problem can be solved in time by an adaptation of the classical algorithm of Johnson [9]. For these results see, Artmeier, Haselmayr, Leucker and Sachenbacher [1], Eisner, Funke and Storandt [6], Brim and Chaloupka [3], and Dorfman, Kaplan, Tarjan and Zwick [5].
The problem becomes much harder when the graph may contain positive-gain cycles. Part of the difficulty is that optimal paths, which are still well-defined, are not necessarily simple and might have to “hop” from one positive-gain cycle to another, until gaining enough charge to head directly to the destination. Hélouët et al. [8] obtained a polynomial time algorithm for the decision problem of determining whether . Dorfman et al. [5] obtained an -time algorithm for the single-source version of the problem, which of course implies an -time algorithm for the all-pairs version.
Our main result is a randomized -time222The hides logarithmic factors. algorithm for solving the all-pairs versions of the maximal final charge problem, and hence also the minimum initial charge problem, improving by a factor for sufficiently dense graphs on the running time of the algorithm of Dorfman et al. [5]. To appreciate our result, we draw a parallel to standard shortest paths. On a graph with nodes and edges (and a suitable potential function), the single source shortest path problem can be solved in time, leading to an all pairs algorithm for dense graphs. A breakthrough result by Williams [11] achieved an time all pairs algorithm, shaving a subpolynomial factor for dense graphs.
All the discussion so far assumed that that battery cannot be recharged at intermediate vertices. A natural variant is obtained when we assume that the battery can be charged at some of the vertices of the graph, with a cost per unit of charge that may vary from vertex to vertex. The goal then, is to find minimum-cost paths within all pairs of vertices in the graph. This problem was considered by Khuller, Malekian and Mestre [10] in the context of conventional, gas-operated, cars, i.e., when all arc costs are positive, and by Dorfman, Kaplan, Tarjan, Thorup and Zwick [4] in the context of electric cars, i.e., when the costs, or gains, can be both positive and negative, and where there might be positive-gain cycles. The main result of Dorfman et al. [4] is a reduction from the all-pairs minimum-cost paths problem to the all-pairs maximal final charges and minimum initial charges problems, and to the standard all-pairs shortest paths problem. Combined with the results of Dorfman et al. [5], this implies an -time algorithm for the all-pairs minimum-cost paths in graphs with no positive-gain cycles. Combined with our result, we obtain a randomized -time algorithm for the all-pairs minimum-cost paths in graphs that may contain positive-gain cycles.
To obtain the improved algorithm we need to introduce many new ideas. We next try to give a rough intuitive description of some of them, ignoring some technicalities that will be dealt with later.
Optimal energetic paths can be very long. (Their length cannot be bounded as a function of alone. A bound must also take the arc gains and the capacity of the battery into account. For more details, see [5].) A natural idea to reduce the length of optimal energetic paths is to introduce shortcuts, i.e., add new arcs that correspond to possibly long paths in the graph. In the standard shortest paths problem, any path in the graph can be used to generate a shortcut, with the gain (or cost) of the arc equal to the sum of the gains of the arcs on the path. This is far from being the case for energetic paths. Consider, for example, a path with and . We cannot add a new arc with to the graph since an electric car with an empty battery would be able to traverse the new arc , but not the original path .
Ignoring some technicalities, we can add a shortcut corresponding to a traversable path in the graph (a path that can be traversed if we start with full battery) if the path is ascending or descending. (See Figure 1(a)-(b).) Given a path , let , for , be the prefix sums of the gains along the path. We say that a path is ascending if , for every , and descending if , for every . If is ascending or descending, then we are allowed to add a shortcut with . For brevity, we refer to ascending or descending paths as monotone.333Note that this does not imply that the prefix sums form a monotone sequence.
Unfortunately, most paths are not monotone. Furthermore, subpaths of monotone paths are not necessarily monotone. There may also be very long paths that do not contain any monotone subpath. We refer to such paths as funnels. Examples of funnels are given in Figure 1-.
Our algorithm constructs monotone paths and funnels and combines them to obtain new monotone paths and funnels until enough information is available to find the optimal energetic paths. The exact details, some of which are quite delicate, appear in the rest of the paper.
Another idea used by our new algorithm is sampling. It is well known that a random set of vertices of size is likely to hit any given path of length at least . Taking advantage of this fact in our context is again much more complicated.
The rest of this extended abstract consists of a technical review of our algorithm and main techniques.
2 Technical Review
A main tool in our algorithm is shortcutting. In the setting of standard shortest paths, any path can be shortcutted to a single arc of gain without affecting the lengths of the shortest paths. Unfortunately, because of the upper and lower bound constraints on the battery, this technique breaks down when applied to energetic paths. That is, by shortcutting arbitrary paths, we may change the optimal energetic paths. For example, assume and let be a graph that is composed of two paths and , where and . Observe that and . On the other hand, by shortcutting the paths and (to arcs of gain ) we will be able to reach from when starting with zero charge. Moreover by using the new gain arc the maximum final charge at (when starting with charge at ) becomes .
The above discussion encourages us to find safe paths that can be shortcutted without affecting the optimal energetic paths (i.e., without affecting the values). We call these paths monotone paths, see Figure 1. Monotone paths are either ascending or descending. An ascending path is a traversable path that satisfies that whenever an electric car traverses , the car has minimum charge at and maximum charge at . A traversable path is a path that does not contain any subpath of gain smaller than (this is equivalent to saying that a car that starts at with full charge can traverse without the charge level going below zero). Similarly, a descending path is a traversable path that satisfies that whenever an electric car traverses , the car has max charge at and minimum charge at (in particular, the gain of a descending path is at least ). A monotone path avoids the two problems mentioned in the previous example: The charge level of an ascending path never drops below the charge level at and therefore the path from the previous example cannot be shortcutted. Moreover, since the charge level remains below the charge level at , shortcutting does not create an alternative path from to that improves the final charge at , similarly to what happened with the path from the previous example.
In the full version of the paper (Theorem ), we prove that in time we can compute a -dimensional table that dominates all simple monotone paths. That is, for every simple monotone path , it holds that . Moreover, the table is sound. That is, for every , if , then there exists a monotone path (not necessarily simple) from to such that . Since monotone paths are traversable, it follows that if , then . Note that it is possible that . Once we have computed , solving the all pairs problem is rather simple, we explain this derivation at the end of the technical review.
The following is a high level description of the computation of . For simplicity, in this short review, we only describe how to dominate ascending paths. A simple observation is that every monotone path contains a monotone subpath of edge-length or . We call such a path a short monotone path. Thus, by shortcutting such a short monotone subpath into a single arc, we get an ascending path of smaller length than and larger or equal gain than . This observation leads to a trivial algorithm: Perform iterations and generate a series of graphs . In the ’th iteration we find for every the largest gain short monotone path from to in . Once we have found all such gains, we build by increasing the gains of every arc444We assume is a full graph by adding arcs of gain . in if there is a corresponding short monotone path from to of a better gain. We can implement each iteration in time using a BST data structure. The table stores the gains of the arcs of final graph . Given a simple ascending path in , this process implicitly constructs a series of paths , where is obtained from by shortcutting as many short monotone paths as possible and is a single arc.555Note that is not uniquely defined since short monotone paths may overlap. Moreover, we might perform shortcuts in because of short monotone paths that appear in and not in .
An immediate question is whether iterations are necessary. The answer is yes. The reason for this are double-funnels (see Figure 2(a)). A path is a double-funnel if does not contain a short monotone subpath. Double-funnels can have edges and an ascending monotone path which consists mainly of a long double-funnel would require iterations to be shortcutted into a single arc, see Figure 2(b).
As a consequence of the discussion above, in order to improve upon the simple algorithm, we need to handle double-funnels and reduce the number of iterations. A simple observation is that every ascending path can be viewed as an alternation between double-funnels (that are maximal with respect to inclusion) and short monotone paths, see Figure 3. Indeed, by the definition of a double-funnel, if we extend a double-funnel that is maximal with respect to inclusion by a single arc, the path ceases to be a double-funnel and therefore contains a short monotone path.
Let be an ascending path such that is not shortcutted to a single arc after iterations of the simple algorithm. Let (paths in , respectively) be the corresponding sequence of ascending paths as we defined before. For every , denote by the number of (maximal with respect to inclusion) double-funnels in . By the interleaving property of double-funnels and short monotone paths, for every , the number of short-monotone subpaths in is at least and therefore (where denotes the number of arcs in a path ). Since is a simple path (and thus of length at most , and since we can uniquely charge a short monotone path that we shortcut at iteration to each funnel in it follows that , so the average number of funnels per iteration (of the iterations that we consider) satisfies . By Markov’s inequality, in at least iterations, . Thus, in at least half of the iterations, the paths have double-funnels. By sampling uniformly at random iterations, we are guaranteed to “hit” such an iteration w.h.p.. The final component of our algorithm is the procedure , that, given a path with double-funnels, finds long shortcuts (i.e., shortcuts that correspond to monotone paths that could be of any length) in , resulting in a path that is shorter than by a constant factor.
Based on the above discussion, our algorithm proceeds as follows. We perform iterations. In each iteration we find all short monotone path and shortcut them (this results in a modified graph with larger arc gains). Moreover, in each iteration, with probability we additionally call Long-Shortcuts which finds long monotone paths in the current graph, shortcuts them, and returns a modified graph.
We now describe the procedure . We extensively use two path structures in Long-Shortcuts: Arc-bounded paths and funnels, see Figure 1. A path is first arc-bounded if for every , it holds that and . A last arc-bounded path is defined analogously. A path is arc-bounded if it is either first or last arc-bounded. A path is a funnel if it is both arc-bounded and a double-funnel. Observe that any double-funnel can be decomposed to two funnels, each starts or ends at the edge of largest gain in absolute value, see Figure 3. Given the current graph , stores a table such that for every , stores the largest recorded gain of a first arc bounded path in that starts with the arc and ends at ( is defined similarly for last arc-bounded paths). Algorithm Long-Shortcuts first generates arc-bounded paths (that is, stores values in the table ) and finally, finds long monotone paths based on those arc bounded paths. To ease the explanation, we begin by demonstrating the latter.
2.1 Generating monotone paths from arc-bounded paths
This part is straightforward: Given a vertex , we consider all arc-bounded paths that start at and we extend each by a single arc: We scan all triplets , such that , and “concatenate” the arc-bounded path that corresponds to with the arc , resulting in a path to that starts with .666We do not actually store paths. Instead we examine the quantity . Assume (other cases are similar). If this concatenated path remains arc bounded then we did not find a monotone path. Otherwise, either or . It is easy to see that in the former case, is ascending (see Figure 4(a)), and in the latter case the subpath from to is descending (see Figure 4(b)). It is easy to see that the running time of this process is .
2.2 Finding arc-bounded paths
As already discusses, any path can be viewed as an alternation between double-funnels (which are just two funnels that are concatenated) and short monotone paths. Thus, handling funnels has a crucial role.
We compute arc bounded paths using two building blocks.
-
1.
A procedure to compute funnels. Given a graph , returns a table that dominates every funnel (which is a simple path) in . That is, for every funnel that is first arc-bounded, it holds that . Similarly, for every funnel that is last arc-bounded, it holds that . Moreover, the table is sound. That is, for every , if , then there exists a first arc-bounded path (not necessarily a funnel) such that . The full details appear in the full version of the paper.
-
2.
A concatenation procedure . Given a graph , a table and a vertex . The procedure, in a brute force manner, scans all 4-tuples of vertices and then tries to concatenate a first arc-bounded path in that start with the arc and end at with first arc-bounded path that start with the arc and end at .777Formally, we look on the quantity and verify some inequalities to make sure that the concatenated path is indeed first arc-bounded. Note that this procedure only generates arc-bounded paths that start at . For the full details, we refer the reader to the full version of the paper. A naive implementation of this procedure takes time. Using a balanced binary search tree, we get a running time of . Since our claimed running time for the entire algorithm is , we can use the Concatenate procedure only times.
We now describe and the intuition about it. The algorithm starts by calling to , which in time computes a table that dominates all simple funnels in . The algorithm then samples uniformly at random sets of size , for . Then, for every and we perform times the procedure . Finally, we extract monotone paths by applying the procedure from Section 2.1 on every vertex in .
We now give the intuition behind the algorithm. Recall the discussion about “hitting” an iteration in which (an ascending path in , for some , that represents the evolution of over the iterations of shortcutting) has at most double-funnels. Assume we run . Every vertex defines a first arc-bounded path , where is maximal such that is first arc-bounded, see Figure 5. Note that may contain several double-funnels, say . Thus, if we apply , times, the table will “find” (that is we will have ). By the discussion in Section 2.1, if we extend by the arc we will find a monotone path of length . For this process to be efficient, we have to balance the work we do (which is proportional to the number of funnels in which is the number of calls to concatenate that we need to do to find ) to compute with the reward we achieve (which is proportional to the length of ) by shortcutting the monotone path corresponding to .
We are shooting for a running time of , therefore as we already said we can call concatenate at most times (recall that it works for a single particular vertex at each call). In particular, for every , the product of and the number of calls of concatenate from each vertex of should be . To explain why we need the levels of sampling, we consider the two extreme cases which our sampling interpolates between. That is, the case of where and the case of where .
These two cases are demonstrated in Figure 5 for a path of length and funnels. The first example (), depicted in Figure 5, considers the case in which all funnels, except for the first one, are of constant length and the rest is filled with the first funnel which is of linear size. Moreover, the arc-bounded paths that correspond (in the manner explained in the previous paragraph) to every vertex in a short funnel are of constant length and the arc-bounded paths that correspond to vertices in the long funnel are all reaching the last arc of the path. Thus, in order to achieve sufficient reward (i.e., find long enough monotone paths), we have to sample a vertex in the long funnel and then perform times . Thus, the example shows that there are cases in which we have to perform concatenations at a single vertex.
The second extreme case, depicted in Figure 5, is the case in which all funnels are of length and for every , the arc-bounded path that corresponds to contains a single funnel. Thus, for every we can apply a single concatenation and find the arc-bounded path that corresponds to and later extend it to a monotone path of length . In this case to reduce the length of by a constant factor, we have to sample vertices (that will hit a constant fraction of the funnels) and perform a constant number of concatenation on each one of them.
2.3 Solving the all-pairs problem
Finally, we briefly describe the key observations that relate monotone paths to the computation of . We begin by assuming that the optimal energetic paths are simple and later show how to solve the general case in which the optimal paths use positive cycles.
2.4 Simple energetic paths
Assume we have computed the table that dominates every simple monotone path in . Let and let be an optimal energetic path from to (that is, ). We consider the special case in which is simple and for every it holds that . That is, the car starts with full charge at and its charge level remains below . We decompose as follows. Let and let be the vertex of lowest gain in . We define to be the vertex of highest gain in the suffix and so on, see Figure 6. This results in a series of vertices . Clearly, this partitioning divides into monotone segments that alternate between ascending and descending paths. A key observation is that these monotone paths are optimal in terms of gain. That is, for every , there is no monotone path from to with larger gain than the subpath . Otherwise, we can replace the subpath by and increase the final charge at ,888We use here the fact that the battery is not full. a contradiction to the optimality of . Thus, for every , it holds that . Let be a directed clique whose gains are defined by . The final observation is that is a funnel in . Thus, by calling we can find this funnel.
2.5 Handling positive cycles
A simple observation is that every positive gain cycle contains a pair of points such that the car can start at with zero charge, and traverse the cycle until it reaches with a fully charged battery (i.e., charge).999It is possible that the car took the direct path in from to , or it cycled through several times. We say that is an entry-exit pair of , where is the entry and is the exit.
We prove in Lemma 6, that every traversable positive cycle contains an entry-exit pair such that , the path from to through , is ascending and , the path from to through , is descending.101010It is possible that . For example in a cycle in which all arc gains are positive. This lemma, leads to a simple algorithm for identifying entry-exit pairs: For every , if and , then set (i.e., is an entry-exit pair). The positive shortcut indicates that there is an ascending path from to . If then clearly we can start at with zero charge and get to with full charge (by using the shortcut111111Recall that using shortcuts does not change the values since each shortcut corresponds to a monotone path in of the same gain. of gain ). Otherwise, the second inequality guarantees that we can start at with zero charge and get back to with positive charge (by using the shortcuts and ). Therefore, by extending the path to , we generate an ascending path with larger gain , see Figure 6. By repeating this multiple times, we get an ascending path from to with gain larger than justifying setting .
We perform additional simple inferences: For every
-
If and , we deduce that the path that consists of the two shortcuts is a witness that . That is, it is possible to start at with zero charge and reach : Either and then the claim follows by the traversability of monotone paths () or and therefore either or . The former case is trivial. In the latter case, we can start with zero charge at and reach with charge and then continue to and reach it with charge.
-
If and , we deduce that .
-
If (so ), we infer that . That is, it is possible to reach if we start at with full charge.
Finally, we combine these relations into a graph and compute its transitive closure . The graph is defined as follows. , where and are two copies of . Each vertex represents being at with charge and each vertex represents being at with full charge. An arc represents that .121212Note that the other direction does not necessarily hold: It is possible that but . We create the arcs according to the relations shown above (for example, if , we add the arc to ). In the full version of the paper (Theorem ), we claim that, w.h.p., for every , if and only if .
Using the graph , our algorithm reduces the all pairs problem to the case in which the energetic paths are simple: For every , using , we find all vertices such that and then, as in Section 2.4, we find the best energetic simple path from any such to .
The following is a brief review of the correctness of the algorithm. Let and let be an optimal energetic path from to (i.e., . We argue that there is a vertex on such that and . If , then we are done since this relation is already recorded in and we can set . Otherwise, let be maximal such that . It follows that and for every it holds that . This implies that must be a simple path.131313Otherwise, contains a positive cycle, so by repeating the cycle (and using the fact that no vertex on cycle, and the rest of the path, has already reached full charge) we can increase the final charge at , a contradiction. So we conclude that the algorithm finds the optimal energetic path when inspecting .
2.6 A technicality - charge drop schedules
In this section we describe Charge drop schedules and the technical challenge that it addresses. Before we delve into the definition, we motivate it by pinpointing several problems with our arguments.
-
1.
Throughout this section we explained how to shortcut an ascending path to single arc via a sequence of short/long shortcut updates. A key invariant that is required for this argument to hold is the fact that given an ascending path , if we replace a monotone subpath of by a monotone path of larger gain, then the resulting path (The stands for concatenation) is ascending and . Unfortunately, this argument does not hold if is descending. For example, consider the graph in Figure 8 and the descending path . After performing one iteration of the simple algorithm (computing all short monotone paths and updating the gains of the graph), we are left with a graph with gain function (see Figure 8) that does not contain any monotone path from to . This is of course unsettling, as finding the best short shortcuts should be a good property of the algorithm and yet it destroyed some other descending paths
-
2.
Recall the procedure that scans all 4-tuples of vertices and then tries to concatenate a first arc-bounded path (stored in ) that starts with the arc and ends at with first arc-bounded path that starts with the arc and ends at (which is done by calculating and verifying some inequalities). Consider the following example: Assume and . Therefore, by running , we will concatenate the arc-bounded paths corresponding to and and get an arc bounded path that starts at and ends at with gain . Unfortunately, this concatenation is not guaranteed to happen. It is possible that earlier in the run of , the algorithm managed to improve to and therefore concatenating to the arc-bounded path corresponding to does not result anymore in an arc-bounded path, see Figure 8. Again, by performing an update that should be good for us (increasing from to ), we hurt ourself somewhere else (we did not make the update ).
In both examples, we suffered from having computed values that are “too good”. The simple concept that solves this problem is charge drop. Charge drops allow us, at any vertex along the path, to get rid of some charge, see Figure 8. Formally, let be a path in . A charge drop schedule is a vector , where . The gain at with respect to and , denoted as is defined as , for and otherwise. Monotone paths and arc bounded paths can be defined similarly to before by replacing the gain of an arc by . When is clear from contexts, we abbreviate and write .
We now show how to fix the two examples using charge drop schedules.
-
1.
In the first example (see Figure 8) is a descending path in , but there is no descending (or ascending) path from to in . Instead, contains the path that has positive gain. By using a simple charge drop schedule that drops units of charge at , we view as a short descending path of gain , see Figure 8.
-
2.
In the second example we faced a problem when trying to concatenate an arc-bounded path corresponding to and an arc bounded path corresponding to . By simply dropping a single unit of charge at (the concatenation point), we are now able to concatenate the two paths and therefore assign , see Figure 8.
We incorporate charge drops in our algorithm in the following places.
-
1.
When computing all short monotone paths, if a path (of length or ) starts by a negative gain arc, we will always apply charge drop schedule and create a descending path out of . For example, if and , then we record a descending path from to of gain (this corresponds to dropping one unit of charge at ).
-
2.
In the computation of long monotone paths. Recall that we consider tuples and we extend the arc-bounded path that corresponds to by the arc . We incorporate charge drops in the following case: If and (that is the concatenated path remains arc-bounded), we record a descending path from to of gain . This corresponds to performing a charge drop at that drops charge.
-
3.
In the concatenation procedure, whenever the concatenation of the two arc bounded paths does not yield an arc-bounded path, we perform a charge drop to force the result to be arc-bounded. That is, for every , if and , we set . This corresponds to performing the smallest possible charge drop at such that the concatenated path is arc-bounded, see Figure 8.
2.7 Main technical lemma
In this section, we prove Lemma 1, a simplified version141414Lemma 1 addresses only ascending paths. of our main lemma. Recall our algorithm: We perform iterations. In each iteration we find all short monotone path and shortcut them (this results in a modified graph with larger arc gains). Moreover, in each iteration, with probability we additionally call Long-Shortcuts which finds long monotone paths in the current graph, shortcuts them, and returns a modified graph.
Lemma 1.
Let be a simple ascending path in . Let be the modified graph after iterations of the modified algorithm and let be its gain function. If , then . If , then w.h.p. there is an ascending path in from to in that satisfies and .
Lemma 1 is derived from Lemma 2, which is our main technical lemma. It provides guarantees about Long-Shortcuts, when run on a graph with an ascending path that contains few double-funnels.
Lemma 2.
Let be a simple ascending path in from to . Let be the number of double-funnels in that are maximal with respect to inclusion. Let be the updated graph resulted from .151515Note that every non empty path contains at least one double-funnel. If , then w.h.p. there is an ascending path in from to that satisfies and .
Proof of Lemma 1.
Let and let be the graphs throughout the iterations of the algorithm. Let be a series of monotone paths, where is the shortest path in from to that has no smaller gain (with respect to ) than (with respect to ). We split the proof into cases.
Case .
Since in each of the rounds we compute all the short monotone paths, and since every monotone path contains a short monotone path, we get that for every , if then . Thus, and the lemma follows.
Case .
If , then we are done. Otherwise and therefore for at least indices , it holds that . This mean that, for each such index , has at most disjoint short shortcuts as subpaths. Thus, by our arguments in the previous sections (see Figure 3), contains double-funnels that are maximal with respect to inclusion. Therefore, w.h.p. we run at an iteration such that contains double-funnels. Hence, the conditions of Lemma 2 are satisfied and we are done.
Before proving Lemma 2, we need to introduce the following structural definitions. These definitions allow us to measure how many applications of Concatenate are needed in order to dominate an arc bounded path.
Definition 3.
Let be a path in . For every we define to be the maximal index such that is first arc-bounded. When is clear from the context, we abbreviate and write .
Definition 4.
Let be a path in . For every , we define as the number of first arc-bounded funnels in that are maximal with respect to inclusion. When is clear from context, we abbreviate and write .
The following lemma proves that for every path , the set of paths is laminar.
Lemma 5.
Let be a path in , then the set of intervals is laminar.
Proof.
Let and let . We show from which the lemma follows. Denote and . Since is -bounded, we have for every . In particular .
Since is -bounded we get that for every . Therefore is -bounded, so by the maximality of we get that , and therefore .
We are now ready to prove Lemma 2.
Proof of Lemma 2.
Let be the disjoint double-funnels in . By the discussion in Section 2, there are arcs in that are not contained in the double-funnels (see Figure 3). Every double-funnel can be decomposed into at most funnels (last arc-bounded followed by first arc-bounded). Let , where , be the corresponding funnels. We distinguish between funnels that are first-arc bounded to those which are last-arc bounded. Assume that the majority of the arcs of belong to first-arc bounded funnels. The analysis for the other case is symmetric. Therefore, these funnels (first-arc bounded) contain at least arcs.161616The choice of and not is due to the subtlety that the disjoint double-funnels do not necessarily cover all of . Among these funnels, we consider only funnels of length at least . Note that at least arcs belong to such funnels (if more than arcs belong to funnels of length at most then we need at least funnels to accommodate them, a contradiction). Denote these arcs by ().
By Lemma 5, the set is laminar. We refer to each item in as an interval. Recall that each interval corresponds to a monotone path of the same length (A maximal arc bounded path extended by a single arc is monotone), see Section 2.1. Moreover, in order for Long-Shortcuts to shortcut the monotone path corresponding to , Long-Shortcuts has to sample and then perform concatenations from .
In the rest of the proof, we prove that Long-Shortcuts finds enough disjoint monotone paths of total length . To this end, we partition into disjoint sets , where correspond to all intervals/monotone paths that require concatenations in order to be realized. We then prove that , the largest of these sets (hence of size ), contains a collection of disjoint chains (a chain is a set of nested intervals) such that:
-
1.
The chains are pairwise internally disjoint. That is, for every and it holds that .
-
2.
, for . This property is crucial for the sampling to “hit” .
-
3.
.
Finally, by Property , we show that w.h.p., for every , Long-Shortcuts realizes an interval from whose length is at least . By combining these disjoint (Property ) shortcuts, we reduce the size of by .
We now show the lower bound on the size of and prove that it contains a collection of chains that satisfy the above poperies. Since is such that for every and (by the laminarity of each interval contains an edge which is not in any other interval) it follows that . Observe that for every , is laminar as a subset of . Moreover, each interval in cannot contain two disjoint intervals in . Indeed, assume and , where all intervals belong to . Therefore , so , a contradiction. It follows that we can decompose (and in particular ) into a collection of internally disjoint chains.
Let be the decomposition of into internally disjoint chains (). Since the ’s are internally disjoint (and so are the funnels in them), . Let be the union of the ’s that satisfy . It follows that
(1) |
Let be the chains of . Let , it holds that
where Inequality follows since and Inequality follows since .
Recall that samples vertices to i.i.d. with probability . Since Long-Shortcuts performs concatenations from every vertex in , every interval in has a probability of to be realized. Let . Since , it follows by the Chernoff bound that w.h.p. we realize an interval from of length at least .
Since are internally disjoint, then the above realized shortcuts (one from every ) are also disjoint. Hence, by shortcutting the realized intervals we get an ascending path in of length.
where Inequality follows from Equation (1) and the last equality holds because, according to the statement of the lemma, .
3 Concluding remarks
We presented a randomized -time algorithm for the finding optimal energetic paths between all-pairs of vertices in a weighted directed -vertex graph with positive and negative gains that may contain positive-gain cycles. This improves upon a previous -time algorithm by Dorfman et al. [5]. The new algorithm is quite involved and requires the introduction of many new ideas. Improving the running time of the algorithm is a natural open problem.
References
- [1] Andreas Artmeier, Julian Haselmayr, Martin Leucker, and Martin Sachenbacher. The shortest path problem revisited: Optimal routing for electric vehicles. KI, 6359:309–316, 2010. doi:10.1007/978-3-642-16111-7_35.
- [2] Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, 16:87–90, 1958.
- [3] Lubos Brim and Jakub Chaloupka. Using strategy improvement to stay alive. Int. J. Found. Comput. Sci., 23(3):585–608, 2012. doi:10.1142/S0129054112400291.
- [4] Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Mikkel Thorup, and Uri Zwick. Minimum-cost paths for electric cars. In 2024 Symposium on Simplicity in Algorithms, SOSA 2024, Alexandria, VA, USA, January 8-10, 2024, pages 374–382. SIAM, 2024. doi:10.1137/1.9781611977936.34.
- [5] Dani Dorfman, Haim Kaplan, Robert Endre Tarjan, and Uri Zwick. Optimal energetic paths for electric cars. In 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, pages 42:1–42:17, 2023. doi:10.4230/LIPICS.ESA.2023.42.
- [6] Jochen Eisner, Stefan Funke, and Sabine Storandt. Optimal route planning for electric vehicles in large networks. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, August 7-11, 2011. AAAI Press, 2011. doi:10.1609/AAAI.V25I1.7991.
- [7] Lester R. Ford. Network flow theory. Technical Report Paper P-923, RAND Corporation, Santa Monica, California, 1956.
- [8] Loïc Hélouët, Nicolas Markey, and Ritam Raha. Reachability games with relaxed energy constraints. arXiv preprint arXiv:1909.07653, 2019.
- [9] Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1):1–13, 1977. doi:10.1145/321992.321993.
- [10] Samir Khuller, Azarakhsh Malekian, and Julián Mestre. To fill or not to fill: The gas station problem. ACM Transactions on Algorithms (TALG), 7(3):1–16, 2011. doi:10.1145/1978782.1978791.
- [11] Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 664–673, 2014. doi:10.1145/2591796.2591811.
Appendix A Entry-Exit Pairs
In this short appendix we prove Lemma 6, which establishes an important property of traversable positive-gain cycles. Specifically, we show that any such cycle can be decomposed into an ascending path followed by a descending path.
Lemma 6.
Let be a traversable positive gain simple cycle in . There exists an entry-exit pair in such that , the path from to through , is ascending and , the path from to through , is descending.
Proof.
Let be an entry-exit of . Consider the path from to itself through . Since is traversable and is an entry, it follows that , i.e., can be traversed when starting at with zero initial charge. Let be the vertex of maximum gain on . Observe that the path from to on is ascending. Indeed the charge level cannot go below the initial charge at (which is zero) and the charge level at is maximum.
If then we are done. Otherwise, consider , the simple path from to through , and let be the vertex of minimum gain in , see Figure 9. By the choice of , , the path from to through , is descending. We now show that is ascending. Since is of minimum gain in , it follows that the gains of the vertices on are nonnegative. Moreover, since is ascending it follows that all gains on are nonnegative. We are left to show that has maximum gain in . Since is ascending, it is enough to show that for every . Let , it follows that . We prove that for every . By contradiction, assume there is such that . Since all gains of vertices in are nonnegative we get that , a contradiction to the definition of .