Shortest Path Algorithms for Functional Environments
This network optimization work is published in the journal “Discrete Optimization.” This research generalizes classic shortest path algorithms to network environments in which arc-costs are governed by functions, rather than fixed weights. 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 generalized. Applications of this work include critical path extensions to solve sequential decision-problems, and generalized network flow with nonlinear gain functions.