  In the $\{-1,0,1\}$-APSP problem the goal is to compute all-pairs shortest
paths (APSP) on a directed graph whose edge weights are all from $\{-1,0,1\}$.
In the (min,max)-product problem the input is two $n\times n$ matrices $A$ and
$B$, and the goal is to output the (min,max)-product of $A$ and $B$.
  This paper provides a new algorithm for the $\{-1,0,1\}$-APSP problem via a
simple reduction to the target-(min,max)-product problem where the input is
three $n\times n$ matrices $A,B$, and $T$, and the goal is to output a Boolean
$n\times n$ matrix $C$ such that the $(i,j)$ entry of $C$ is 1 if and only if
the $(i,j)$ entry of the (min,max)-product of $A$ and $B$ is exactly the
$(i,j)$ entry of the target matrix $T$. If (min,max)-product can be solved in
$T_{MM}(n) = \Omega(n^2)$ time then it is straightforward to solve
target-(min,max)-product in $O(T_{MM}(n))$ time. Thus, given the recent result
of Bringmann, K\"unnemann, and Wegrzycki [STOC 2019], the $\{-1,0,1\}$-APSP
problem can be solved in the same time needed for solving approximate APSP on
graphs with positive weights.
  Moreover, we design a simple algorithm for target-(min,max)-product when the
inputs are restricted to the family of inputs generated by our reduction. Using
fast rectangular matrix multiplication, the new algorithm is faster than the
current best known algorithm for (min,max)-product.

Data Structures and Algorithms