# Optimal energetic paths for electric cars

Dani Dorfman Blavatnik School of Computer Science, Tel Aviv University,
Israel. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>Work of Uri
Zwick partially supported by grant 2854/20 of the Israeli Science Foundation.
Haim Kaplan∗ Robert E. Tarjan Department of Computer Science, Princeton
University. Email<EMAIL_ADDRESS>Partially supported by a gift from
Microsoft. Uri Zwick∗

###### Abstract

A weighted directed graph $G=(V,A,c)$, where $A\subseteq V\times V$ and
$c:A\to\mathbb{R}$, naturally describes a road network in which an electric
car can roam. An arc $uv\in A$ models a road segment connecting the two
vertices (junctions) $u$ and $v$. The cost $c(uv)$ of the arc $uv$ is the
amount of _energy_ the electric car needs to travel from $u$ to $v$. This
amount may be positive, zero or negative. To make the problem realistic, we
assume that there are no negative cycles in the graph.

The electric car has a battery that can store up to $B$ units of energy. The
car can traverse an arc $uv\in A$ only if it is at $u$ and the charge $b$ in
its battery satisfies $b\geq c(uv)$. If the car traverses the arc $uv$ then it
reaches $v$ with a charge of $\min\\{b-c(uv),B\\}$ in its battery. Arcs with a
positive cost deplete the battery while arcs with negative costs charge the
battery, but not above its capacity of $B$. If the car is at a vertex $u$ and
cannot traverse any outgoing arcs of $u$, then it is stuck and cannot continue
traveling.

We consider the following natural problem: Given two vertices $s,t\in V$, can
the car travel from $s$ to $t$, starting at $s$ with an initial charge $b$,
where $0\leq b\leq B$? If so, what is the maximum charge with which the car
can reach $t$? Equivalently, what is the smallest $\delta_{B,b}(s,t)$ such
that the car can reach $t$ with a charge of $b-\delta_{B,b}(s,t)$ in its
battery, and which path should the car follow to achieve this? We refer to
$\delta_{B,b}(s,t)$ as the _energetic cost_ of traveling from $s$ to $t$. We
let $\delta_{B,b}(s,t)=\infty$ if the car cannot travel from $s$ to $t$
starting with an initial charge of $b$. The problem of computing energetic
costs is a strict generalization of the standard shortest paths problem.

We show that the single-source version of the minimum energetic paths problem
can be solved using simple, but subtle, adaptations of the classical Bellman-
Ford and Dijkstra algorithms. To make Dijkstra’s algorithm work in the
presence of negative arc costs, but no negative cycles, we use a variant of
the $A^{*}$ search heuristic. This is similar to the idea used by Johnson to
solve the standard all-pairs shortest paths problem. These results are
explicit or implicit in some previous papers. We provide a clearer, simpler
and unified description of these algorithms.

##  1 Introduction

A weighted directed graph $G=(V,A,c)$, where $A\subseteq V\times V$ and
$c:A\to\mathbb{R}$, naturally describes a road network in which an electric
car can roam. An arc $uv\in A$ models a road segment connecting the two
vertices (junctions) $u$ and $v$. The cost $c(uv)$ of the arc $uv$ is the
amount of _energy_ the electric car needs to travel from $u$ to $v$. This
amount may be positive, e.g., if the road segment is uphill or level; zero; or
negative, e.g., if the road segment is downhill. To make the problem realistic
we assume that there are no negative cycles in the graph.

An electric car is equipped with a battery that can store up to $B$ units of
energy, where $B>0$ is a parameter. We assume that the electric car cannot be
charged along the way and has to rely on the initial charge available in its
battery. If the car is currently at vertex $u$ with charge $b$ in its battery,
where $0\leq b\leq B$, then it can traverse an arc $uv\in A$ if and only if
$c(uv)\leq b$. If this condition holds, and the car traverses the arc, then it
reaches $v$ with a charge of $\min\\{b-c(uv),B\\}$. In particular, the car can
traverse $uv$ if $b-c(uv)>B$ (which can hold only if $c(uv)<0$), but the
battery does not charge beyond its capacity of $B$. We may assume that
$c(uv)\in[-B,B]$ for every $uv\in A$, as arcs with $c(uv)>B$ can never be
used, and thus can be removed, and costs $c(uv)<-B$ can be changed to
$c(uv)=-B$.

We consider the following natural problem: Given two vertices $s,t\in V$, can
the car travel from $s$ to $t$, starting at $s$ with an initial charge $b$,
where $0\leq b\leq B$? If so, what is the maximum charge with which the car
can reach $t$? Equivalently, what is the smallest $\delta_{B,b}(s,t)$ such
that the car can reach $t$ with a charge of $b-\delta_{B,b}(s,t)$ in its
battery, and which path should the car follow to achieve this? We refer to
$\delta_{B,b}(s,t)$ as the _energetic cost_ of traveling from $s$ to $t$. We
let $\delta_{B,b}(s,t)=\infty$ if the car cannot travel from $s$ to $t$
starting with an initial charge of $b$. Note that the energetic cost depends
on the capacity $B$ of the battery and on the initial charge $b$ of the
battery at $s$. Increasing the capacity $B$ of the battery cannot increase
energetic costs. Increasing the initial charge $b$, on the other hand, can
either decrease or increase the energetic cost $\delta_{B,b}(s,t)$. If the
initial charge $b$ is not large enough, the car will not be able to travel
from $s$ to $t$, i.e., $\delta_{B,b}(s,t)=\infty$, or the car may be forced to
use energetically expensive detours.111For example, a two-arc path with costs
$b$ and $-b$, for some $b>0$, modeling a mountain crossing, has an energetic
cost of $0$, but it can be used only if the initial charge of the battery is
at least $b$. On the other hand, if the battery is almost fully charged, i.e.,
$b$ is close to $B$, the car will not be able to take full advantage of
downhill segments in the beginning the journey. In such cases increasing $b$
may also increase $\delta_{B,b}(s,t)$.

We also consider the related problem of finding the _minimum initial change_
at $s$ that will allow the car to travel to $t$. We denote this quantity by
$\beta_{B}(s,t)$. Note that $\beta_{B}(s,t)$ is the smallest $b$ for which
$\delta_{B,b}(s,t)<\infty$, or $\beta_{B}(s,t)=\infty$ if there is no such
$b$. We show that this problem is equivalent to computing energetic costs on
the _reverse_ graph.

If all arc costs are non-negative, then $\delta_{B,b}(s,t)=\delta(s,t)$, if
$\delta(s,t)\leq b\leq B$, where $\delta(s,t)$ is the standard distance from
$s$ to $t$ in the graph $G$. Otherwise, $\delta_{B,b}(s,t)=\infty$. More
generally, even in the presence of negative arc costs, but no negative cycles,
$\delta_{B,b}(s,t)=\delta(s,t)$ if and only if there exists a shortest path
$P$ from $s$ to $t$ such that the length of every prefix of $P$ is in the
interval $[b-B,b]$. In general, energetic costs may be larger than distances,
since the charge in the battery is constrained to remain in the interval
$[0,B]$, i.e., it is not allowed to go negative and it is capped at $B$. (For
example, the electric car may not be able to traverse a mountain pass and may
need to take a detour.) We do always have $\delta_{B,b}(s,t)\geq\delta(s,t)$.

The problem of computing minimum energetic costs is thus a strict
generalization of the standard shortest paths problem. We show, however, that
the single-source version of the energetic cost problem can still be solved
using simple, but sometimes subtle, adaptations of the classical Bellman-Ford
[3, 15] and Dijkstra [10] algorithms. To make Dijkstra’s algorithm work in the
presence of negative arc costs but no negative cycles, we use a variant of the
$A^{*}$ search heuristic (see, e.g., Hart et al. [21]). This is similar to the
idea used by Johnson [22] to solve the standard all-pairs shortest paths
problem.

Unlike the standard shortest paths problem, the single-target version of the
energetic costs problem is _not_ equivalent to the single-source version. In
particular, We cannot solve the single-target problem by running the adapted
Bellman-Ford and Dijkstra algorithms backward. Although there is always a tree
of minimum energetic-cost paths from a source vertex $s$ to all other vertices
reachable from it, there are simple examples in which there is no tree of
minimum energetic-cost paths to a target vertex $t$, from all vertices that
can reach it.

As mentioned in the abstract, the versions of the Bellman-Ford and Dijkstra
algorithms presented here are explicit or implicit in some previous papers.
Some other papers describe versions that are not as efficient as the versions
described here. We try to present and prove the correctness of these two
algorithms in the simplest and clearest possible way.

###  1.1 Our results

We show that the single-source version of the minimum energetic paths problem
can be solved in $\mathrm{O}(mn)$ time using a simple adaptation of the
Bellman-Ford [3, 15] algorithm, where $m=|A|$ and $n=|V|$. Furthermore, if a
_valid potential function_ $p:V\to\mathbb{R}$ is given, i.e., a function for
which $c(uv)-p(u)+p(v)\geq 0$ for every $uv\in A$, then the single-source
version can be solved in $\mathrm{O}(m+n\log n)$ time using an adaptation of
Dijkstra’s [10] algorithm similar to $A^{*}$ search (see, e.g., Hart et al.
[21]). Since a valid potential function can be found in $\mathrm{O}(mn)$ time
using the standard Bellman-Ford algorithm, the all-pairs version of the
minimum energetic paths problem can be solved $\mathrm{O}(mn+n^{2}\log n)$
time, essentially matching the bound for the standard APSP problem.

###  1.2 Related results

Various adaptations of the Bellman-Ford and Dijkstra algorithms for problems
similar to or equivalent to the minimum energetic paths problem defined here
were given by several authors. Artmeier et al. [1] give versions that run in
$\mathrm{O}(n^{3})$ and $\mathrm{O}(n^{2})$ time, respectively. Brim and
Chalupka [5] give versions of these algorithms with the same running times as
ours, but their descriptions of the algorithms are not easy to follow, as they
define the problem differently and use some non-natural conventions, and the
algorithms are only described as parts of a more complicated algorithm for the
solution of one-player and two-player _energy games_. (For more on energy
games, see also Brim et al. [6] and Dorfman et al. [12].) Baum et al. [2] give
a version of Dijkstra’s algorithm but with a much slower running time. They
also show that the maximum charge with which $t$ can be reached when starting
at $s$ with charge $b$ is a piece-wise linear function of $b$ with at most
$\mathrm{O}(n)$ breakpoints.

Khuller et al. [23] consider a related problem in which the battery (or the
fuel tank) can be recharged at intermediate vertices, with a possibly
different price per unit of charge at each intermediate vertex. All arc costs
are non-negative. They give various algorithms for computing a cheapest path
from $s$ to $t$. Among these algorithms is a $\mathrm{O}(n^{2}\Delta\log
n)$-time algorithm for the single-target version, where $\Delta$ is a bound on
the number of rechargings allowed, and an $\mathrm{O}(n^{3}\Delta^{2})$-time
algorithm for the all-pairs version.

Several authors, including Lehmann [25], Tarjan [29] and Mohri [27] considered
generalized versions of the shortest paths problem defined by _semirings_. If
$(R,\oplus,\otimes)$ is a semiring and $P$ is an $s$-$t$ path whose arcs have
costs $c_{i}$, the cost of $P$ is defined to be $c(P)=\otimes_{i=1}^{k}c_{i}$.
The goal is to find $\oplus_{P}\,c(P)$, where $P$ ranges over all $s$-$t$
paths, assuming this quantity is well defined. The standard shortest paths
problem corresponds to the _tropical_ semiring $(\mathbb{R},\min,+)$. All
these results assume, as part of the definition of a semiring, that $\otimes$
is associative. Thus, as we shall see, none of these results apply to our
problem, as our operation $\otimes$ is not associative.

Generalized versions of Dijkstra’s algorithm were obtained by various authors,
most notably by Knuth [24]. These generalization are of a different nature and
are apparently not related to the version given here.

Other non-standard versions of the shortest paths problem were also
considered. Perhaps the most famous one is the _bottleneck_ shortest paths
problem. See, e.g., [17, 8] for the single-pair version, and [32, 13] for the
all-pairs version. Vassilevska [31] considered an interesting non-standard
_non-decreasing_ version of the shortest paths problem related to reading
train schedules. Finally, Madani et al. [26] considered the _discounted_
shortest paths problem. All these problems are quite different from the
problem considered here.

###  1.3 Organization of the paper

In the next section we formally define the minimum energetic paths problem. In
Section 3 we describe the modified version of the Bellman-Ford algorithm [3,
15]. In Section 4 we describe the modified version of Dijkstra’s algorithm
[10]. In Section 5 we consider two closely related problem, minimum _initial-
energy_ paths and maximum _final-energy_ paths. We end in Section 6 with some
concluding remarks and open problems.

##  2 Minimum energetic paths

To simplify the presentation, we concentrate on the computation of
$\delta_{B}(s,t)=\delta_{B,B}(s,t)$, i.e., the energetic cost of traveling
from $s$ to $t$ when starting with a fully charged battery of capacity $B$.
There is a simple reduction from the problem of computing $\delta_{B,b}(s,t)$,
for an arbitrary $0\leq b\leq B$, to that of computing $\delta_{B}(s,t)$: Add
a new vertex $s^{\prime}$ and an arc $s^{\prime}s$ of cost
$c(s^{\prime}s)=B-b$. Then, it is easy to see that
$\delta_{B,b}(s,t)=\delta_{B}(s^{\prime},t)-(B-b)$. A similar idea can be
incorporated directly into the algorithms that we describe.

We begin with a definition of the energetic cost of a path.

######  Definition 2.1 (Energetic cost of a path).

If a path $P=u_{0}u_{1}\ldots u_{k}$ is traversable, when starting from
$u_{0}$ with a fully charged battery of capacity $B$, then the final charge in
the battery when reaching $u_{k}$ is $B-d_{B}(P)$, where $d_{B}(P)$ is defined
to be the the _energetic cost_ of the path. Note that $0\leq d_{B}(P)\leq B$.
If the path is not traversable, we let $d_{B}(P)=\infty$.

To obtain a simple formula for $d_{B}(P)$ we define the following operations:

$x\oplus_{B}y\;=\;[x+y]_{\,0}^{B}\quad,\quad[z]_{\,0}^{B}\;=\;\left\\{\begin{array}[]{cl}0&\mbox{if
$z<0$}\\\ z&\mbox{if $0\leq z\leq B$}\\\
\infty&\mbox{otherwise}\end{array}\right.$

We assume that $x+\infty=\infty+x=\infty$ for every
$x\in[-B,B]\cup\\{\infty\\}$. For brevity, we sometimes write $x\oplus y$
instead of $x\oplus_{B}y$ when $B$ is understood from the context. 222Note
that $\oplus$ is not related to the semiring framework mentioned in Section
1.2. Note that for every $x,y\in\mathbb{R}$ and $B>0$ we have $x+y\leq
x\oplus_{B}y$. It is important to note that $\oplus_{B}$ is _not_ associative.
(For example, $B\oplus(B\oplus-B)=B$ while $(B\oplus B)\oplus-B=\infty$, and
$(-1\oplus-2)\oplus 2=2$ while $-1\oplus(-2\oplus 2)=0$, assuming $B\geq 2$.)

######  Lemma 2.2.

Let $P=u_{0}u_{1}\ldots u_{k}$ be a directed path, let $P^{\prime}=u_{0}\ldots
u_{k-1}$, and let $c_{i}=c(u_{i-1}u_{i})$, for $i=0,1,\ldots,k$. Let $B$ be
the capacity and initial charge of battery at $u_{0}$. If $k=0$ then
$d_{B}(P)=0$. If $k>0$ then

$d_{B}(P)\;=\;d_{B}(P^{\prime})\oplus c_{k}\;=\;((\cdots((0\oplus c_{1})\oplus
c_{2})\oplus\cdots)\oplus c_{k-1})\oplus c_{k}\;.$

###### Proof.

Let $b_{i}$ be the charge of the battery at $u_{i}$ and let $d_{i}=B-b_{i}$ be
the _depletion_ of the battery at $u_{i}$, for $i=0,1,\ldots,k$. Clearly
$d_{0}=0$. It is easy to prove by induction that
$d_{i}=d_{i-1}\oplus_{B}c_{i}$ and the lemma follows. ∎

As mentioned, the operation $\oplus_{B}$ is _not_ associative. Thus, in
general, $d_{B}(P)\neq
0\oplus(c_{1}\oplus(\cdots\oplus(c_{k-2}\oplus(c_{k-1}\oplus c_{k}))\cdots))$.
In Section 5 we show, however that
$c_{1}\oplus(c_{2}\oplus(\cdots\oplus(c_{k-1}\oplus(c_{k}\oplus 0))\cdots))$
also has an interesting meaning.

######  Definition 2.3 (Energetic costs, minimum energetic paths).

The _energetic cost_ $\delta_{B}(s,t)$ of traveling from $s$ to $t$ when
starting from $s$ with a fully charged battery of capacity $B$ is defined as

$\delta_{B}(s,t)\;=\;\min\\{\,d_{B}(P)\mid\mbox{$P$ is an $s$-$t$ path
in~{}$G$}\,\\}\;.$

If $\delta_{B}(s,t)<\infty$ and $P$ is an $s$-$t$ path satisfying
$\delta_{B}(s,t)=d_{B}(P)$, then $P$ is said to be a _minimum energetic path_
from $s$ to $t$.

Since we assume that there are no negative cycles in the graph, it is easy to
see that for every path $P$ from $s$ to $t$ there is a simple path
$P^{\prime}$ such that $d_{B}(P^{\prime})\leq d_{B}(P)$. (For this to hold it
is in fact enough to require that there are no traversable negative cycles in
the graph.) Thus, the minimum in the definition above can be taken over simple
paths only.

It is interesting to note that $\delta_{B}(s,t)$ is well-defined also in the
presence of traversable negative cycles, but minimum energetic paths are not
necessarily simple in this case. In a companion paper [11] we obtain efficient
algorithms that work in the presence of negative cycles. These algorithms,
however, are substantially more complicated than the algorithms presented here
and rely on new algorithmic techniques.

It is not difficult to see, and it will also follow from the correctness of
the algorithms that we present in the next sections, that for every source
vertex $s\in V$ there is always a tree of minimum energetic paths to all other
vertices that can be reached from it. The simple example given in Figure 1
shows that a tree of minimum energetic paths to a given target vertex $t$ does
not always exist.

Figure 1: A simple but illustrative example. Assume $B\geq 3$. The two numbers
next to each vertex $u$ are $\delta_{B}(s,u)$ and $\delta_{B}(u,t)$. The bold
arcs constitute a tree of minimum energetic paths from the source vertex $s$
to all other vertices. Another such tree can be obtained by replacing the arc
$ct$ by $bt$. On the other hand, the only minimum path from $a$ to $t$ is
$abct$, while the only minimum path from $b$ to $t$ is the arc $bt$. Thus,
there is no tree of minimum paths to $t$ from all other vertices.

##  3 An energetic version of the Bellman-Ford algorithm

Recall that for any $x$ and $y$, $x\oplus_{B}y\geq x+y$. This implies that in
a graph without negative cycles, if there is a traversable path from $s$ to
$t$, there is such a path that is simple and hence contains at most $n-1$
arcs. This means that if there are no negative cycles, we can solve the
single-source minimum energetic paths problem using the Ford-Bellman [3, 15]
shortest path algorithm: We merely replace $+$ by $\oplus_{B}$.

We base our description of the algorithm on that in [30], which uses a queue
as suggested by Gilsinn and Witzgall [18].

The algorithm maintains a tentative energetic cost $d(v)$ for each vertex $v$,
equal to the minimum of the energetic costs of paths from $s$ to $v$ found so
far. Initially $d(s)=0$ and $d(v)=\infty$ for $v\neq s$, where $s$ is the
source. It also maintains a queue $Q$, initially containing $s$. The algorithm
repeats the following step until $Q$ is empty:

> Scan a vertex: Delete the front vertex $u$ on $Q$. For each arc $uv$, if
> $\delta(u)\oplus_{B}c(uv)<\delta(v)$, _relax_ $uv$: Set
> $\delta(v)\leftarrow\delta(u)\oplus_{B}c(uv)$, set $\pi(v)\leftarrow u$, and
> add $v$ to the back of $Q$ if it is not on $Q$.

Pseudocode of the algorithm, which we call e-BF, is given on the left of
Figure 2. The correctness proof and analysis of the standard Bellman-Ford
algorithm in the absence of negative cycles (see e.g., Tarjan [30]) translates
directly to this version.

######  Theorem 3.1.

If $G=(V,A,c)$ has no traversable negative cycles then e-BF finds minimum
energetic paths from $s$ to all vertices in $\mathrm{O}(mn)$ time.

###### Proof.

We define _passes_ over the queue. Pass $0$ is the first scan step of $s$.
Given that pass $k$ is defined, pass $k+1$ is the sequence of scan steps of
vertices added to $Q$ during pass $k$. A straightforward induction on $k$
shows that for each vertex $v$ that has a minimum-energy path of at most $k$
arcs, $d(v)$ is the energetic cost of such a path after $k$ passes. It follows
that the energetic costs are correctly computed. The $\pi$ values computed
describe a tree of minimum-energy paths from $s$ to all vertices reachable
from $s$ using a fully charged battery of capacity $B$. Since each pass takes
$\mathrm{O}(m)$ time, the total time of the algorithm is $\mathrm{O}(mn)$. ∎

In addition to the non-existence of negative cycles, the only thing required
for correctness of the algorithm is that $\oplus_{B}$ is non-decreasing in its
second argument: If $y\leq z$, $x\oplus y\leq x\oplus z$.

As in the standard version of the Bellman-Ford algorithm, one can add _subtree
disassembly_ [28, 9], which does not improve the worst-case time bound but is
likely to speed up the algorithm in practice. It is also easy to modify the
algorithm so that it would find a traversable negative cycle that can be
reached from $s$, if any.

_$\mbox{\sl e-BF\/}(G=(V,A,c),B,s)$_ :

for  _$u\in V$_ do

$d(u)\leftarrow\infty$

$\pi(u)\leftarrow null$

$d(s)\leftarrow 0$

$Q\leftarrow\mbox{{\it Queue}}()$

$Q.\mbox{{\it insert\/}-{\it last}}(s)$

while  _$Q\neq\emptyset$_ :

$u\leftarrow Q.DeleteFirst()$

for  _$uv\in A$_ do

if  _$d(v) >d(u)\oplus_{B}c(uv)$_ :

$d(v)\leftarrow d(u)\oplus_{B}c(uv)$

$\pi(v)\leftarrow u$

if  _$v\notin Q$_ :

$Q.InsertLast(v)$

return $d$

_$\mbox{\sl e-Dijkstra\/}(G=(V,A,c),p,B,s)$_ :

for  _$u\in V$_ do

$d(u)\leftarrow\infty$

$\pi(u)\leftarrow null$

$b(s)\leftarrow 0$

$H\leftarrow\mbox{{\it min\/}-{\it heap}}()$

$H.\mbox{{\it insert}}(s,p(s))$

while  _$H\neq\emptyset$_ :

$v\leftarrow H.\mbox{{\it delete\/}-{\it min}}()$

for  _$uv\in A$_ do

if  _$d(v) >d(u)\oplus_{B}c(uv)$_ :

$d(v)\leftarrow d(u)\oplus_{B}c(uv)$

$\pi(v)\leftarrow u$

if  _$v\notin H$_ :

$H.\mbox{{\it insert}}(u,d(v)+p(v))$

else:

$H.\mbox{{\it decrease\/}-{\it key}}(u,d(v)+p(v))$

return $d$

Figure 2: Energetic variants of the Bellman-Ford and Dijkstra algorithms.

The correctness of e-BF implies the following corollary, which we use to the
prove the correctness of the energetic variant of Dijkstra’s algorithm:

######  Corollary 3.2.

If each $d(v)<\infty$ corresponds to the energetic cost of some path from $s$
to $v$, and $d(v)\leq d(u)\oplus_{B}c(uv)$ for every $uv\in A$, then
$d(v)=\delta_{B}(s,v)$, for every $v\in V$.

##  4 An energetic version of Dijkstra’s algorithm

If all arc costs are non-negative, Dijkstra’s algorithm [10] with $\oplus_{B}$
replacing $+$ will solve the one-source problem. This algorithm replaces the
queue $Q$ in the Bellman-Ford algorithm with a heap $H$. The key of a vertex
$v$ in the heap is $d(v)$. Each scan step deletes a vertex of minimum key from
the heap. When a relaxation decreases the key of a vertex in the heap, the
algorithm does the appropriate _decrease-key_ operation on the heap. If all
arc costs are non-negative, the algorithm deletes each vertex from $H$ at most
once, and when a vertex $v$ is deleted from $H$, $d(v)$ is the minimum
energetic cost of a path from $s$ to $v$. The proof of correctness mimics that
of the standard Dijsktra algorithm. The algorithm does at most $n$ heap
insertions, at most $n$ heap deletions, and at most $m$ decrease-key
operations. If the heap is a Fibonacci heap [16] or equally efficient data
structure, e.g., [20], the total running time is $\mathrm{O}(m+n\log n)$. In
fact, the algorithm is identical to the standard algorithm with $d(v)$ values
greater than $B$ replaced by $\infty$.

More interesting is that if arc costs can be negative but there are no
negative cycles, we can use a variant of the $A^{*}$ search algorithm, which
is a modification of Dijkstra’s algorithm, to solve the one-source minimum
energetic paths problem in $\mathrm{O}(m+n\log n)$ time, provided that we have
a _valid potential function_ $p:V\to\mathbb{R}$. A potential $p$ is _valid_ if
$c(uv)-p(u)+p(v)\geq 0$ for every arc $uv\in A$. It is well-known that a valid
potential function exists if and only if the graph contains no negative
cycles.

The $A^{*}$ search algorithm is almost identical to Dijkstra’s algorithm. The
only difference is that the _key_ of vertex $v$ in the heap is $d(v)+p(v)$,
and not just $d(v)$, where $p$ is a valid potential function. In the original
setting of the $A^{*}$ search heuristic, $p(v)$ is an estimate of the distance
from $v$ to the destination $t$. The correctness of the algorithm only
requires, however, that $p$ is a valid potential function. If $p$ is valid,
the $A^{*}$ algorithm deletes each vertex $v$ at most once from the heap, and
when $v$ is deleted, $d(v)=\delta_{B}(s,v)$, the energetic cost of traveling
from $s$ to $v$.

An energetic version of the $A^{*}$ is obtained simply by replacing $+$ by
$\oplus_{B}$ in relaxations. We assume the algorithm is given a potential $p$
that is valid for $+$, not $\oplus_{B}$. The algorithm begins with $d(s)=0$
and $d(v)=\infty$ for each vertex $v\in V\setminus\\{s\\}$, and $H$ containing
$s$. The key of a vertex $v$ in $H$ is $d(v)+p(v)$. The algorithm repeats the
following step until $H$ is empty:

> Scan a vertex: Delete from $H$ a vertex $u$ with minimum key $d(u)+p(u)$.
> For each arc $uv$, if $d(u)\oplus_{B}c(uv)<d(v)$, _relax_ $uv$: Set
> $d(v)\leftarrow d(u)\oplus_{B}c(uv)$; $\pi(v)\leftarrow u$; add $v$ to $H$
> with key $d(v)+p(v)$ if $v\notin H$, or decrease the key of $v$ to
> $d(v)+p(v)$ if $v\in H$.

Pseudocode of the resulting algorithm, which we call e-Dijkstra, is given on
the right of Figure 2. The main step towards establishing the correctness of
e-Dijkstra is the following:

######  Lemma 4.1.

If $p$ is a valid potential then e-Dijkstra maintains the following invariant:
if $u$ has been deleted from $H$ while $v$ has not been deleted from $H$ yet,
then $d(u)+p(u)\leq d(v)+p(v)$. As a consequence, each vertex $u$ is inserted
and deleted from $H$ at most once.

###### Proof.

We prove the lemma by induction on the number of heap operations. The lemma is
true initially, as no vertex was deleted from $H$ yet. Suppose it is true just
before $u$ is deleted from $H$. Since $d(u)+p(u)$ is _minimum_ among all $u\in
H$, and since $d(u)=\infty$ for all vertices not yet inserted into $H$, the
invariant holds just after $u$ is deleted from $H$. By the induction
hypothesis, $d(u)+p(u)$ is now _maximum_ over all $u$ already deleted from
$H$. Suppose the invariant holds just before the relaxation of an arc $uv$.
Just after the relaxation, $d(v)=d(u)\oplus_{B}c(uv)\geq d(u)+c(uv)$. Hence

$d(v)+p(v)\;\geq\;d(u)+c(uv)+p(v)\;\geq\;d(u)+p(u)\;,$

where the last inequality follows by the validity of $p$. Since the relaxation
strictly decreased $d(v)$, it follows that $v$ could not have already been
deleted from $H$, as it would violate the claim that $d(u)+p(u)$ is maximum
over all vertices already deleted from $H$. Thus, $v$ is either in $H$ or was
not inserted into $H$ yet. Decreasing the key of $v$ to $d(v)+p(v)$, or
inserting $v$ to $H$ with this key does not violate the invariant. ∎

The proof of Lemma 4.1 is the same as the proof of the corresponding lemma for
the standard version of $A^{*}$ except for the use of the inequality
$x\oplus_{B}y\geq x+y$. Using Lemma 4.1 we can easily prove the correctness of
the algorithm.

######  Theorem 4.2.

If $G=(V,A,c)$ has no negative cycles and $p$ is a valid potential for $G$,
then e-Dijkstra finds minimum energetic paths from $s$ to all vertices in
$\mathrm{O}(m+n\log n)$ time.

###### Proof.

When a vertex $u$ is removed from $H$, all outgoing arcs $uv$ are scanned and
all appropriate relax operations are performed. By Lemma 4.1, $d(u)$ will not
be changed again. Thus, when the algorithm terminates $d(v)\leq
d(u)\oplus_{B}c(uv)$ for every arc $uv\in A$. By Corollary 3.2, we have
$d(v)=\delta_{B}(s,v)$, for every $v\in V$. As in the proof of Theorem 3.1 we
get that the $\pi$ values describe a tree of minimum energetic paths from $s$
to all vertices that can be reached from $s$.

The algorithm performs at most $n$ heap insertions, at most $n$ heap
deletions, and at most $m$ decrease-key operations. With an efficient heap
implementation the total running time is $\mathrm{O}(m+n\log n)$. ∎

The remaining question is how to obtain a valid potential. For this we can use
any standard shortest path algorithm: If $s$ is an arbitrary source from which
all vertices are reachable, there are no negative cycles, and
$p(v)=-\delta(s,v)$, where $\delta(s,v)$ is the standard distance from $s$ to
$v$, then $c(uv)-p(u)+p(v)\geq 0$, for every arc $uv$, by the triangle
inequality. (If there is no such vertex $s$ in the graph, add a new vertex $s$
and connect it with zero-cost arcs to all other vertices.)

Thus we can compute minimum energetic paths from $k$ sources in
$\mathrm{O}(m+n\log n)$ time per source plus the time to solve one standard
one-source shortest path problem with the given arc costs. The extra time
needed for this preprocessing is $\mathrm{O}(mn)$ if we use Bellman-Ford,
$\mathrm{O}(mn^{1/2}\log C)$ if we use Goldberg’s [19] shortest path
algorithm, or $\mathrm{O}(m\log^{2}n\log(nC)\log\log n)$ time if we use the
improvement by Bringmann et al. [7] of the recent breakthrough result of
Bernstein et al. [4]; the latter two bounds require integer arc costs no
smaller than $-C$. With any one of these choices, we obtain the following
corollary:

######  Corollary 4.3.

The all-pairs minimum energetic paths in a graph $G=(V,A,c)$ with no negative
cycles can be solved in $\mathrm{O}(mn+n^{2}\log n)$ time.

The resulting all-pairs algorithm is very similar to Johnson’s [22] algorithm
for the standard all-pairs shortest paths problem. The slight advantage of
using the $A^{*}$ formulation, as we have done, is that no explicit
transformation of arc costs is needed, only a simple modification of heap
keys. A potential transformation of arc costs was also used by Edmonds and
Karp [14].

##  5 Minimum initial charges and maximum final charges

To end the paper, we consider two problems that are closely related to the
minimum energetic paths problem. Let $G=(V,A,c)$ be a graph with no
(traversable) negative cycles and let $B$ be the capacity of the battery. For
two vertices $s,t\in V$, we let $\alpha_{B}(s,t)$ be the _maximum final
charge_ with which it is possible to reach $t$ when starting at $s$ with a
full battery, or $-\infty$, if it is not possible to travel from $s$ to $t$.
We also let $\beta_{B}(s,t)$ be the _minimum initial charge_ required at $s$
for getting to $t$, or $\infty$, if no initial charge (of at most $B$) is
sufficient.

The maximum final charge problem is not really a new problem as
$\alpha_{B}(s,t)=B-\delta_{B}(s,t)$. As noted in the introduction,
$\beta_{B}(s,t)$ is the smallest $b$ such that $\delta_{B,b}(s,t)\leq b$, or
equivalently $\delta_{B,b}(s,t)<\infty$, if there is such a $b$. Thus, if $B$
and all arc costs are integral, then $\beta_{B}(s,t)$, for a specific pair $s$
and $t$, can solved using binary search.

There is, however, a more interesting relation between the minimum initial-
charge problem and the minimum energetic cost problem. Namely,
$\beta_{B}(s,t)$ is equal to
$\delta^{\mathop{\hbox{}{G}}\limits^{\,{}_{\leftarrow}}}_{B}(t,s)$ the
energetic cost of traveling from $t$ to $s$ in the _reversed graph_
$\mathop{\hbox{}{G}}\limits^{\,{}_{\leftarrow}}$, the graph obtained by
reversing all the arcs in the graph $G$ and retaining all arc costs. This
relation follows easily from the following lemma, analogous to Lemma 2.2,
whose simple proof is omitted. For a path $P$ from $s$ to $t$, let $b_{B}(P)$
be the minimum initial charge at $s$ with which the path $P$ can be traversed.

######  Lemma 5.1.

Let $P=u_{0}u_{1}\ldots u_{k}$ be a directed path, let $P^{\prime}=u_{1}\ldots
u_{k}$, and let $c_{i}=c(u_{i-1}u_{i})$, for $i=1,\ldots,k$. Let $B$ be the
capacity of the battery. If $k=0$ then $b_{B}(P)=0$. If $k>0$ then

$b_{B}(P)\;=\;c_{1}\oplus_{B}b_{B}(P^{\prime})\;=\;c_{1}\oplus(c_{2}\oplus(\cdots\oplus(c_{k-1}\oplus(c_{k}\oplus
0))\cdots))\;.$

######  Corollary 5.2.

For every $s,t\in V$,
$\beta_{B}(s,t)=\delta^{\mathop{\hbox{}{G}}\limits^{\,{}_{\leftarrow}}}_{B}(t,s)$.

As immediate corollaries, it follows that we can solve the single-target
version of the minimum initial-charge paths problem in $\mathrm{O}(m+n\log n)$
time, if we are given a valid potential, and the all-pairs version of the
problem in $\mathrm{O}(mn+n^{2}\log n)$.

##  6 Concluding remarks and open problems

Our goal was to present simple algorithm for solving the minimum energetic
paths problem in the absence of negative cycles. Most of the results in this
paper are not new. Our formulation of the minimum energetic paths problem,
which we believe helps simplify and clarify the results and their relation to
standard shortest paths algorithms, seems to be new, however. The simple
relation between minimum energetic paths and minimum initial-charge paths also
seems to be new.

An interesting feature of the minimum energetic paths problem is that it is
not symmetric, i.e., the single-target version of the problem is not
equivalent to the single-source version. The best algorithm that we currently
have for the single-target version actually solves the all-pairs version of
the problem. It would be interesting to know whether there is a more efficient
solution. The fact that there may not be a tree of minimum energetic paths to
a given target may indicate that the single-target version is harder than the
single-source version.

In a companion paper [11] we extend some of the results presented here to the
setting in which negative cycles may be present. The algorithms required in
that case are much more complicated.

## 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.
  * [2] Moritz Baum, Julian Dibbelt, Thomas Pajor, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf.  Energy-optimal routes for battery electric vehicles.  Algorithmica, 82:1490–1546, 2020.
  * [3] Richard Bellman.  On a routing problem.  Quarterly of Applied Mathematics, 16:87–90, 1958.
  * [4] Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen.  Negative-weight single-source shortest paths in near-linear time.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 600–611. IEEE, 2022.
  * [5] Lubos Brim and Jakub Chaloupka.  Using strategy improvement to stay alive.  Int. J. Found. Comput. Sci., 23(3):585–608, 2012.
  * [6] Lubos Brim, Jakub Chaloupka, Laurent Doyen, Raffaella Gentilini, and Jean-François Raskin.  Faster algorithms for mean-payoff games.  Formal methods in system design, 38(2):97–118, 2011.
  * [7] Karl Bringmann, Alejandro Cassis, and Nick Fischer.  Negative-weight single-source shortest paths in near-linear time: Now faster!  CoRR, abs/2304.05279, 2023.
  * [8] Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, and Uri Zwick.  Bottleneck Paths and Trees and Deterministic Graphical Games.  In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), pages 27:1–27:13, 2016.
  * [9] Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan, and Renato F. Werneck.  Shortest-path feasibility algorithms: An experimental evaluation.  ACM J. Exp. Algorithmics, 14, 2009.
  * [10] Edsger W. Dijkstra.  A note on two problems in connexion with graphs.  Numerische Mathematik, 1:269–271, 1959.
  * [11] Dani Dorfman, Haim Kaplan, Robert E. Tarjan, and Uri Zwick.  Optimal energetic paths in the presence of negative cycles.  In preparation, 2023.
  * [12] Dani Dorfman, Haim Kaplan, and Uri Zwick.  A faster deterministic exponential time algorithm for energy games and mean payoff games.  In Proc. of 46th ICALP, volume 132 of LIPIcs, pages 114:1–114:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [13] Ran Duan and Seth Pettie.  Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths.  In Proc. of 20th SODA, pages 384–391, 2009.
  * [14] Jack Edmonds and Richard M. Karp.  Theoretical improvements in algorithmic efficiency for network flow problems.  J. ACM, 19(2):248–264, 1972.
  * [15] Lester R. Ford.  Network flow theory.  Technical Report Paper P-923, RAND Corporation, Santa Monica, California, 1956.
  * [16] Michael L. Fredman and Robert Endre Tarjan.  Fibonacci heaps and their uses in improved network optimization algorithms.  Journal of the ACM, 34(3):596–615, 1987.
  * [17] Harold N. Gabow and Robert E. Tarjan.  Algorithms for two bottleneck optimization problems.  Journal of Algorithms, 9(3):411–417, 1988.
  * [18] Judith F. Gilsinn and Christoph Witzgall.  A performance comparison of labeling algorithms for calculating shortest path trees.  Technical Report 772, US National Bureau of Standards, 1973.
  * [19] Andrew V. Goldberg.  Scaling algorithms for the shortest paths problem.  SIAM J. Comput., 24(3):494–504, 1995.
  * [20] Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, and Uri Zwick.  Hollow heaps.  ACM Trans. Algorithms, 13(3):42:1–42:27, 2017.
  * [21] Peter E. Hart, Nils J. Nilsson, and Bertram Raphael.  A formal basis for the heuristic determination of minimum cost paths.  IEEE Trans. Syst. Sci. Cybern., 4(2):100–107, 1968.
  * [22] Donald B. Johnson.  Efficient algorithms for shortest paths in sparse networks.  Journal of the ACM, 24(1):1–13, 1977.
  * [23] 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.
  * [24] Donald E. Knuth.  A generalization of Dijkstra’s algorithm.  Information Processing Letters, 6(1):1–5, 1977.
  * [25] Daniel J. Lehmann.  Algebraic structures for transitive closure.  Theor. Comput. Sci., 4(1):59–76, 1977.
  * [26] Omid Madani, Mikkel Thorup, and Uri Zwick.  Discounted deterministic markov decision processes and discounted all-pairs shortest paths.  ACM Trans. Algorithms, 6(2):33:1–33:25, 2010.
  * [27] Mehryar Mohri.  Semiring frameworks and algorithms for shortest-distance problems.  J. Autom. Lang. Comb., 7(3):321–350, 2002.
  * [28] Robert E. Tarjan.  Shortest paths.  Technical report, AT&T Bell Laboratories, 1981.
  * [29] Robert E. Tarjan.  A unified approach to path problems.  Journal of the ACM, 28(3):577–593, 1981.
  * [30] Robert E. Tarjan.  Data structures and network algorithms.  SIAM, 1983.
  * [31] Virginia Vassilevska.  Nondecreasing paths in a weighted graph or: how to optimally read a train schedule.  In Proc. of 19th SODA, pages 465–472, 2008.
  * [32] Virginia Vassilevska, Ryan Williams, and Raphael Yuster.  All pairs bottleneck paths and max-min matrix products in truly subcubic time.  Theory Comput., 5(1):173–189, 2009.