Shortest path algorithms for functional environments

This research generalises classic shortest path algorithms to network environments in which arc‐costs are governed by functions, rather than fixed weights. We show that the asymptotic efficiency of our algorithms is identical to their classic counterparts. Previous results, since Knuth in 1976, require several restrictive assumptions on the functions permitted in the network. In contrast, our algorithms require only monotonicity. We present examples illustrating that this is the largest class of functions to which classic algorithms can be generalised. Applications of this work include critical path extensions to solve sequential decision‐problems, and generalised network flow with nonlinear gain functions.