ALGORITHMS FOR THE CONSTRAINED QUICKEST PATH PROBLEM AND THE ENUMERATION OF QUICKEST PATHS

The quickest path problem, which was originally proposed by Chen and C hin,is a variant of the shortest path problem. Its objective is to fin d quickest paths in a network to transmit a given amount of data such that the transmission time is minimized. If the quickest paths are req uired to go through a specified path, then the restricted problem is c alled the constrained quickest path problem. In this paper, for all pa irs of nodes in a network N, an O(mn(2)) time algorithm is first prese nted to find constrained quickest paths, and then an O(k(2)mn(2)) time algorithm is presented to enumerate-the first k quickest paths. Our r esults improve previous results by Rosen, Sun and Xue.