  In this paper, we present an improved algorithm for the All Pairs
Non-decreasing Paths (APNP) problem on weighted simple digraphs, which has
running time $\tilde{O}(n^{\frac{3 + \omega}{2}}) = \tilde{O}(n^{2.686})$. Here
$n$ is the number of vertices, and $\omega < 2.373$ is the exponent of time
complexity of fast matrix multiplication [Williams 2012, Le Gall 2014]. This
matches the current best upper bound for $(\max, \min)$-matrix product [Duan,
Pettie 2009] which is reducible to APNP. Thus, further improvement for APNP
will imply a faster algorithm for $(\max, \min)$-matrix product. The previous
best upper bound for APNP on weighted digraphs was $\tilde{O}(n^{\frac{1}{2}(3
+ \frac{3 - \omega}{\omega + 1} + \omega)}) = \tilde{O}(n^{2.78})$ [Duan, Gu,
Zhang 2018]. We also show an $\tilde{O}(n^2)$ time algorithm for APNP in
undirected graphs which also reaches optimal within logarithmic factors.
