The all-pairs quickest path problem (Q2366074): Difference between revisions

The quickest path problem, proposed by \textit{Y. L. Chen} and \textit{Y. N. Chin} [Comput. Oper. Res. 17, No. 2, 153-161 (1990; Zbl 0698.90083)], is defined as follows. We have a communication network \(N=(V,A,c.l)\), where \(G=(V,A)\) is a directed graph without multiple arcs and self-loops, \(c(u,v)\geq 0\) is the capacity of an arc \((u,v)\in A\), and \(l(u,v)\geq 0\) is the lead time of an arc \((u,v)\in A\). For an arc \((u,v)\), the capacity \(c(u,v)\) denotes the maximum number of data units which can be transmitted from node \(u\) to node \(v\) per unit time, and \(l(u,v)\) denotes the lead time required to send data from node \(u\) to node \(v\). If \(\sigma\geq 0\) units of data are transmitted from node \(u\) through arc \((u,v)\), then the required transmission time is \(l(u,v)+(\sigma/c(u,v))\). Let \(\rho(u_ 1,u_ 2,\dots,u_ k)\) be a path from \(u_ 1\) to \(u_ k\). Then the lead time \(l(p)\) along the path \(p\) is \(l(p)=\sum_{i=1}^{k-1} l(u_ i,u_{i+1})\) and the capacity \(c(p)\) of path \(p\) is \(c(p)=\min_{1\leq i\leq k-1} c(u_ i,u_{i+1})\). To send \(\sigma\) units of data from \(u_ 1\) to \(u_ k\) through path \(p\), the total transmission time required is \(T_ p(\sigma)=l(p)+\sigma/c(p)\). Given nodes \(s\) and \(t\), the quickest path problem is to find a path \(p\) from \(s\) to \(t\), such that the total transmission time to send \(\sigma\geq 0\) units of data from \(s\) to \(t\) is minimum among all possible paths from \(s\) to \(t\) in the network \(N\). This problem is a variant of the shortest path problem. But the optimality property of shortest paths no longer holds. That is, if \(p\) is a shortest path from \(u\) to \(v\), then any subpath of \(p\) must itself be shortest. In this paper the all-pairs quickest path problem as a function of \(\sigma\) is discussed. That is, we preprocess the network in such a way that given any pair of nodes \(u\), \(v\) and any amount of data \(\sigma\geq 0\), report the quickest path to transmit the data from \(u\) to \(v\). Throughout this paper, \(n\) will denote the number of nodes \(| V|\), \(m\) will denote the number of arcs \(| A|\), and \(r\) will denote the number of distinct capacities. The preprocessing time is \(O(mn^ 2)\) or \(O(rmn+rn^ 2\log n)\) if \(r\) is small,space is \(O(rn^ 2)\), and query time for a pair of nodes is \(O(\log r)\) plus the number of arcs of the actual path if it is to be reported.