Consider a network 𝒩=(G,c,τ) where G=(N,A) is a directed graph and cij and τij, respectively, denote the capacity and the transmission time of arc (i,j)∈A. The quickest flow problem is then to determine for a given value ν the minimum number T(ν) of time units that are necessary to transmit (send) ν units of flow in 𝒩 from a given source s to a given sink s'. In this paper the authors show that the quickest flow problem is closely related to the maximum dynamic flow problem and to linear fractional programming problems. Based on these relationships they develop several polynomial algorithms and a strongly polynomial algorithm for the quickest flow problem. Finally the authors report computational results on the practical behaviour of the present methods. It turns out that some of them are practically very efficient and well-suited for solving large problem instances.
