  The goal of this paper is to design a simplex algorithm for linear programs
on lattice polytopes that traces `short' simplex paths from any given vertex to
an optimal one. We consider a lattice polytope $P$ contained in $[0,k]^n$ and
defined via $m$ linear inequalities. Our first contribution is a simplex
algorithm that reaches an optimal vertex by tracing a path along the edges of
$P$ of length in $O(n^4 k\log(nk)$. The length of this path is independent from
$m$ and it is the best possible up to a polynomial function. In fact, it is
only polynomially far from the worst-case diameter, which roughly grows as a
linear function in $n$ and $k$.
  Motivated by the fact that most known lattice polytopes are defined via
$0,\pm 1$ constraint matrices, our second contribution is an iterative
algorithm which exploits the largest absolute value $\alpha$ of the entries in
the constraint matrix. We show that the length of the simplex path generated by
the iterative algorithm is in $O(n^2k \log(nk\alpha))$. In particular, if
$\alpha$ is bounded by a polynomial in $n, k$, then the length of the simplex
path is in $O(n^2k \log(nk))$.
  For both algorithms, the number of arithmetic operations needed to compute
the next vertex in the path is polynomial in $n$, $m$ and $\log k$. If $k$ is
polynomially bounded by $n$ and $m$, the algorithm runs in strongly polynomial
time.
