On the quickest path problem (Q1261485)

The problem of finding the all-pairs quickest path (between every pair of nodes) in an \(N\) input network is analyzed \((N=(V,A,C,L),| V|=n,| A|=m\) are numbers of nodes and arcs respectively, \(C(u,v)\) and \(L(u,v)\) are capacity and lead time respectively). An algorithm is presented to solve the problem for a given \(\sigma\) (the amount of data being transmitted). It is shown that the quickest path between any 2 nodes for a \(\sigma\) can be found in \(O(\log m)\) time, providing \(O(mn)^ 2\) preprocessing time.