An algorithm for finding the \(k\) quickest paths in a network (Q1201855)

The traditional shortest path problem is to find a shortest path from the source node \(s\) to the sink node \(t\) in a network where each arc has only one attribute ``distance'' associated with it. Although this is a useful model to solve many practical problems, there are situations where this model is inappropriate because each arc of the network has multiple attributes. For example, in a communication network, the transmission time between two connected nodes depends on not only the distance but also the capacity. Therefore, the author and \textit{Y. H. Chin} [Comput. Oper. Res. 17, No. 2, 153-161 (1990; Zbl 0698.90083)] defined the quickest path as a problem of finding a minimum transmission time path from node \(s\) to node \(t\) in a network where each arc has two attributes, one is the lead time and the other is the capacity. In this paper, the author further extends the quickest path problem such that the first \(k\) quickest looping paths are enumerated instead of simply a single quickest path. Let \(n\) and \(m\) denote the numbers of nodes and arcs in the network. Then the algorithm proposed in this paper has time complexity of \(O(m^ 2+(m+k)n \log n+k^{1.5} \log k)\). If \(O(k)=O(m)\), then the proposed algorithm can be run in time of \(O(m^ 2+mn \log n)\), which is identical to the time required by the most efficient algorithm to find a single quickest path. In other words, if \(O(k)\leq O(m)\), then our algorithm for finding the first \(k\) quickest paths is as efficient as the best known algorithm for finding a single quickest path.