A simple approach to nondecreasing paths

We present a simple reduction of the problem of nondecreasing paths (with minimal last edge weight) in a directed edge-weighted graph to a reachability problem in a directed unweighted graph. The reduction yields an alternative simple method of solving the single-source nondecreasing paths problem in almost linear time. If the edge weights are integers then our algorithm can be implemented in O((n+m)log⁡log⁡n) time on the word RAM, where n and m stand for the number of vertices and edges in the input graph, respectively. By using the reduction, we obtain also a simple algorithm for the all-pairs nondecreasing paths problem. It runs in O˜(n^ωmin⁡{aw_G^ω,W_G}) time, where aw_G denotes the average number of distinct weights of edges incident to the same vertex while W_G stands for the total number of distinct edge weights in the input graph G, and ω is the exponent of fast matrix multiplication.