$\{-1,0,1\}$-APSP and (min,max)-Product Problems

Hodaya Barr, Tsvi Kopelowitz, Ely Porat +1

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 p…