Parametric shortest path algorithms with an application to cyclic staffing

AbstractLet G=(V, E) be a digraph with n vertices including a special vertex s. Let E′ ⊆ E be a designated subset of edges. For each e ϵ E there is an associated real number ƒ1(e). Furthermore, let ƒ2(e)=1 if e ϵ E′ and ƒ2(e)=0 if e ϵ E − E′. The length of edge e is ƒ1(e)− λƒ2(e), where λ is a parameter that takes on real values. Thus the length varies additively in λ for each edge of E′.We shall present two algorithms for computing the shortest path from s to each vertex υ ϵ V parametrically in the parameter λ, with respective running times O(n3) and O(n|E|log n). For dense digraphs the running time of the former algorithm is comparable to the fastest (non-parametric) shortest path algorithm known.This work generalizes the results of Karp [2] concerning the minimum cycle mean of a digraph, which reduces to the case that E′=E. Furthermore, the second parametric algorithm may be used in conjunction with a transformation given by Bartholdi, Orlin, and Ratliff [1] to give an O(n2 log n) algorithm for the cyclic staffing problem