  In this paper, we study algorithms for special cases of energy games, a class
of turn-based games on graphs that show up in the quantitative analysis of
reactive systems. In an energy game, the vertices of a weighted directed graph
belong either to Alice or to Bob. A token is moved to a next vertex by the
player controlling its current location, and its energy is changed by the
weight of the edge. Given a fixed starting vertex and initial energy, Alice
wins the game if the energy of the token remains nonnegative at every moment.
If the energy goes below zero at some point, then Bob wins. The problem of
determining the winner in an energy game lies in $\mathsf{NP} \cap
\mathsf{coNP}$. It is a long standing open problem whether a polynomial time
algorithm for this problem exists.
  We devise new algorithms for three special cases of the problem. The first
two results focus on the single-player version, where either Alice or Bob
controls the whole game graph. We develop an $\tilde{O}(n^\omega W^\omega)$
time algorithm for a game graph controlled by Alice, by providing a reduction
to the All-Pairs Nonnegative Prefix Paths problem (APNP). Thus we study the
APNP problem separately, for which we develop an $\tilde{O}(n^\omega W^\omega)$
time algorithm. For both problems, we improve over the state of the art of
$\tilde O(mn)$ for small $W$. For the APNP problem, we also provide a
conditional lower bound which states that there is no $O(n^{3-\epsilon})$ time
algorithm for any $\epsilon > 0$, unless the APSP Hypothesis fails. For a game
graph controlled by Bob, we obtain a near-linear time algorithm. Regarding our
third result, we present a variant of the value iteration algorithm, and we
prove that it gives an $O(mn)$ time algorithm for game graphs without negative
cycles, which improves a previous upper bound.
