The quickest path problem (Q912765)

The authors consider the following modification of shortest path problems: let a digraph with n nodes and m arcs be given. For any arc (u,v) we have its lead time l(u,v) and its capacity c(u,v). The transmission time for \(\sigma\) units of data along this arc is defined as \(t(u,v):=l(u,v)+\sigma /c(u,v)\). The quickest path problem asks for a path from the source to the sink along which the sum of transmission times is minimum. For fixed \(\sigma\), the authors state an algorithm of time complexity \(O(m^ 2+mn \log m)\) to solve the quickest path problem. If a quickest path for any arbitrary \(\sigma\) is looked for, then the network can be preprocessed in \(O(m^ 2+mn \log m)\) time such that finding a quickest path requires only O(log m) additional steps.