LAUSR

The quickest path problem consists of finding a path in a directed network to transmit a given amount $$\sigma $$σ of items from a source node to a sink node with minimal transmission time, where the transmission time depends on the traversal times $$\tau $$τ and the capacities u of the arcs. We suppose that there exist more than one quickest path and finds a quickest path with a special property. In this paper, first, some algorithms to find a quickest path with minimum capacity, minimum lead time, and min-max arc lead time are presented, which runs in $$O(r(m+n \log n))$$O(r(m+nlogn)) and $$ O((r(m+n \log n))\log r') $$O((r(m+nlogn))logr′) time, where r and $$ r' $$r′ are the number of distinct capacity and lead time values and m and n are the number of arcs and nodes in the given network. Then, we suppose that values $$\sigma , \tau $$σ,τ and u change to $$\sigma ', \tau '$$σ′,τ′, and $$u'$$u′. The purpose is to find a quickest path such that it has the minimum transmission time value among all quickest paths, by changing $$\sigma $$σ to $$\sigma '$$σ′, $$\tau $$τ to $$\tau '$$τ′, or u to $$u'$$u′. We show that some of these problems are solved in strongly polynomial time and the others remain as open problems.